快速排序

快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

核心代码

 1 int Sort(int arr[],int nLow,int nHigh)
 2 {
 3     int temp = arr[nLow];
 4 
 5     while(nLow < nHigh)
 6     {
 7         //从后向前找第一个比标准值小的
 8         while(nLow < nHigh)
 9         {
10             if(arr[nHigh] < temp)
11             {
12                 arr[nLow] = arr[nHigh];
13                 nLow++;
14                 break;
15             }
16             else
17             {
18                 nHigh--;
19             }
20         }
21 
22         //从前向后找第一个比标准值大的
23         while(nLow < nHigh)
24         {
25             if(arr[nLow] > temp)
26             {
27                 arr[nHigh] = arr[nLow];
28                 nHigh--;
29                 break;
30             }
31             else
32             {
33                 nLow++;
34             }
35         }
36     }
37 
38     //标准值放入
39     arr[nLow] = temp;
40 
41     //返回标准值位置
42     return nLow;
43 }
44 
45 void QuickSort(int arr[],int nLow,int nHigh)
46 {
47     int nStandard;
48     
49     //检测参数
50     assert(arr!=NULL && nLow<=nHigh);
51 
52     //找标准值位置
53     nStandard = Sort(arr,nLow,nHigh);
54 
55     //数组分成两部分 分别执行以上操作
56     QuickSort(arr,nLow,nStandard-1);
57     QuickSort(arr,nStandard+1,nHigh);
58 }

算法分析：

　　最好时间复杂度：O(nlog2(n))

　　平均时间复杂度：O(nlog2(n))

　　最坏时间复杂度：O(n^2)　　　　有序

　　　　空间复杂度：log2(n)

　　　　　　稳定性：不稳定