数据结构：快排
注：所有的快排针对无重复大量数据是很快的，但是针对有重复大量数据的排序是很慢的；
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题，有异曲同工之妙，但是题型和写法完全不同，希望诸君仔细体会；
注：并不是故意的将所有的快排都列为不稳定；而是边界及判断问题，确实是学习的一大难点