快速排序:
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:
任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
快速排序有三个版本,将一一实现。
Hoare版本:
直接上动图理解:
当前为一遍快排。
再分别以key左右两边进行相同的排序
直到key = right = left。
综上得用递归思想。
代码如下:
void QuickSort(int* a, int begin,int end)
{if (begin >= end)//递归返回条件{return;}int right = end;int left = begin;int key = begin;while (begin < end){//找小while (begin<end && a[end]>=a[key]){end--;}//找大while (begin<end && a[begin]<=a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[key], &a[begin]);k = begin;QuickSort(a,left,key-1);//key左边递归QuickSort(a,key+1,right);//key右边递归
}
递归展开图:
优化代码:
通过画递归展开图后,发现如果这个k的取值一直等于left,有缺点,递归的次数较多。
如果能改进就能让效率提高。
改进思路:
如果这个递归能像二叉树一样,总共只需要N*log(N)次,就只需要每次这个k取值去一个中间值,不需要去最大也不需要取最小。
这样的改进方案,称之为三数取中。
像刚刚,如果要递归的话一次需要递归9次,如果每次取中间的值当k,每次只需要递归3次 。
等左边递归结束式左边空间还是可以继续利用的。
代码如下:
int GetMid(int* a, int begin, int end)
{int mid = (begin+end) / 2;if (a[mid] > a[end]){if (a[mid] < a[begin]){return mid;}else if (a[end] > a[begin]){return end;}elsereturn begin;}else{if (a[mid] > a[begin]){return mid;}else if (a[end] < a[begin]){return end;}elsereturn begin;}
}
void QuickSort(int* a, int begin,int end)
{if (begin >= end)//递归返回条件{return;}//三数取中int mid = GetMid(a, begin, end);swap(&a[mid], &a[begin]);int right = end;int left = begin;int key = begin;while (begin < end){//找小while (begin<end && a[end]>=a[key]){end--;}//找大while (begin<end && a[begin]<=a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[key], &a[begin]);key = begin;QuickSort(a,left,key-1);//key左边递归QuickSort(a,key+1,right);//key右边递归
}
挖坑法版本:
代码如下:
void QuickSort2(int* a, int begin, int end)
{if (begin >= end)//递归返回条件{return;}//三数取中int mid = GetMid(a, begin, end);swap(&a[mid], &a[begin]);int left = begin;int right = end;int key = a[left];int hole = left;//第一个为坑while (begin < end){//找小while (begin < end && a[end] >= key){end--;}//找到小的后将数据移到刚刚坑位,并将当前位置作为坑a[hole] = a[end];hole = end;//找大while (begin < end && a[begin] <= key){begin++;}//找到大的后将数据移到刚刚坑位,并将当前位置作为坑a[hole] = a[begin];hole = begin;}a[hole] = key;QuickSort(a, left, hole - 1);//key左边递归QuickSort(a, hole + 1, right);//key右边递归
}
前后指针法:
cur找小,找到以后prev+1后交换cur和prev。
等cur == n-1之后,将a[key]和a[prev]交换,并且将key = prev。
这个过程保证了prev和cur之间的值是大于key的。
代码如下:
void QuickSort3(int* a, int begin,int end)
{if (begin>=end)//递归返回条件{return;}//三数取中int mid = GetMid(a, begin, end);swap(&a[mid], &a[begin]);int prev = begin;int cur = prev + 1;int key = prev;while (cur<=end-begin){if (a[cur] < a[key]){prev++;if (prev < cur){swap(&a[prev],&a[cur]);}}cur++;}swap(&a[key], &a[prev]);key = prev;QuickSort(a, begin, key - 1);//key左边递归QuickSort(a, key + 1, end);//key右边递归
}