快速排序

快速排序

从小到大

思想：先2分块，确定基准元素，保证块之间有序，也就是说 左块任意数字小于右块任意数字，块内无序，再对每一块分2块，层层递归；

优化：减少基准元素值的交换次数，先找到两个位置 ，左边大于基准元素，右边小于基准元素，两个值交换，直至遍历所有数字后，才基准元素交换；

关于递归优化不是太明白，优化前是quickSort函数两次递归，优化后一次递归，应该是在这里减少了堆栈深度。

撸代码：

 1#include<stdio.h>
 2#include<iostream>
 3using namespace std;
 4int Partition(int a[],int low,int hight)
 5{
 6    int pivotKey=a[low];/**基准元素值（枢轴）*/
 7    while(low<hight)
 8    {
 9        while(low<hight&&a[hight]>=pivotKey)/**从右开始，若小于基准元素，则交换位置*/
10            hight--;
11        swap(a[low],a[hight]);/**小于基准元素的值跑到左边*/
12        while(low<hight&&a[low]<=pivotKey)/**从左开始*/
13            low++;
14        swap(a[low],a[hight]);
15    }
16    return low;
17}
18
19/*******优化 不必要的交换（还可优化基准元素的选取，防止选到极大极小值）*********/
20/*数组中分三次取样，每次取三个数，三个样品中各取出中间数，然后在这三个中枢当中再取一个中间数作为枢轴*/
21int Partition1(int a[],int low,int hight)
22{
23    int startIndex=low;/**基准元素只交换一次*/
24    int pivotKey=a[low];
25    while(low<hight)
26    {
27        while(low<hight&&a[hight]>=pivotKey)
28            hight--;
29        while(low<hight&&a[low]<=pivotKey)
30            low++;
31        swap(a[low],a[hight]);/**找到左边大的，右边小的 ，交换一次*/
32    }
33    /**循环执行完，左小右大，low就是基准元素该去的位置*/
34    swap(a[low],a[startIndex]);
35    return low;
36}
37
38
39void quickSort(int a[],int low,int hight)
40{
41    int pivot;
42    if(low<hight)
43    {
44        pivot=Partition(a,low,hight);/**基准元素下标*/
45        quickSort(a,low,pivot-1);/**分块排序，保证块之间有序*/
46        quickSort(a,pivot+1,hight);
47    }
48
49    /*********递归优化：减少堆栈深度**********/
50    /*
51    while(low<hight)
52    {
53        pivot=Partition(a,low,hight);
54        quickSort(a,low,pivot-1);
55        low=pivot+1;
56    }
57    */
58
59}
60int main()
61{
62    int a[10]={5, 1, 9, 3, 7, 4, 8, 6, 2};
63    int n=9;
64    quickSort(a,0,n-1);/**从小到大排序*/
65    for(int i=0;i<n;i++)
66        printf("%d ",a[i]);
67    return 0;
68}