数据结构：快排
注：所有的快排针对无重复大量数据是很快的，但是针对有重复大量数据的排序是很慢的；
1.霍尔(hoare)版本
时间复杂度:O（N*logN）
稳定性：不稳定；在fun()函数while判断时一不小心就会存在越界和和死循环问题；
霍尔版本的快排，代码如下：主要实现再func()和quick()函数中
int func(int arr[],int left,int right) {
int key = left;//取最左边的值；或最右边的值是一样的；
while (left < right) {//相遇就结束了
//右边找小
while (left < right && arr[right] >= arr[key])right--;//越界和死循环问题
//左边找大
while (left < right && arr[left] <= arr[key])left++;
swap(arr[left], arr[right]);
}
//相遇之后，left==right；再交换
swap(arr[left], arr[key]);//如何保证相遇之时的值比keyi小，因为是right先走的，用它来保证
//right先走，停下来的位置一定比key小或者相遇，L停下来是相遇或比key大,
//因为取值是在最左边取的值，已知arr[left]==arr[key];
//如果left先走，走到相遇，需要再比较一下
//如果right先走，相遇之时就代表已经没有比key大的了
return right;
}
void quicksort(int arr[],int begin,int end) {
if (begin>=end) return; //结束条件判断；
int key=func(arr, begin, end);
//[begin,key-1]key[key+1,end]
quicksort(arr,begin, key - 1);
quicksort(arr, key + 1, end);
}
int main()
{
int a[10] = { 9,8,7,6,5,4,3,2,1,0 };
int right = sizeof(a) / sizeof(int)-1;
int left = 0;
quicksort(a, left, right);
for (auto x : a) cout << x << endl;
return 0;
}
2.挖坑法版本
叙述：将key位置(要比较的那个数)的数值保存起来，还是从右边找小，将小的放到坑里，再从左边找大，再放到小的那个坑里，相遇之时再把剩的key值放坑里;左边为坑右边找，右边为坑左边找，相遇之时就是坑，再把key的值放进去
时间复杂度:O（N*logN）
稳定性：不稳定；在fun()函数while判断时一不小心就会存在越界和和死循环问题；
只写实现方法，其余按照霍尔版本的代码写，程序可以照常运行
int func(int arr[],int left,int right) {
int key = arr[left];//将要比较的值保存起来；
int hole = left;//将坑挖出来
while (left < right)
{//右边找小
while (left < right && arr[right] >= key) right--;
arr[hole] = arr[right];
hole = right;
//左边找大
while (left < right && arr[left] <= key)left++;
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}3.双指针版本
时间复杂度:O（N*logN）
稳定性：不稳定；
int func(int arr[],int left,int right) {
int key = left;
int prev = left;
int cur = left+1;
while (cur <= right){
if (arr[cur] < arr[key] && ++prev != cur)swap(arr[prev], arr[cur]);
cur++;
}
swap(arr[prev], arr[key]);
key = prev;
return key;
}这三种类型的快排，都是以最左边的arr[0]作为判断依据，不停的排序；在实际应用中，可以采取三点取中法来作为比较依据；代码是要改变的；
越无序，重复性越小的数据，使用此三种快排都可以；在实际应用中，就是双指针法最为稳妥；代码量最少
可是对于重复性特别大的数据，一般采用三指针法快排，来操作
力扣：283题，有异曲同工之妙，但是题型和写法完全不同，希望诸君仔细体会；
注：并不是故意的将所有的快排都列为不稳定；而是边界及判断问题，确实是学习的一大难点
原文地址：https://blog.csdn.net/qincjun/article/details/142853999
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！