一.基本思想
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
二.Hoare法
假设我们让最左边为keyi（注意这个表示的是下标），且要排升序；
1.若最左边为keyi，则right先走，找比arr[keyi]小的，left后走，找比arr[keyi]大的，然后right与left交换；
当left和right相遇时，结束循环，最后交换arr[keyi]和arr[left]；
再让keyi=left，接着递归它的左子列和右子列；
2.若最右边为keyi，则left先走，找比arr[keyi]大的，right后走，找比arr[keyi]小的，然后right与left交换；
当left和right相遇时，结束循环，最后交换arr[keyi]和arr[left]；
再让keyi=right，接着递归它的左子列和右子列；
注意这里的keyi，left，right都是下标。
左子列的区间是begin到keyi-1；
右子列的区间是keyi+1到end；
动态演示
1. void QuickSort(int* arr, int left,int right) 2. { 3. 4. if (left >= right) 5. return; 6. int begain = left; 7. int end = right; 8. int keyi= left; 9. while (left < right) 10. { 11. //这里要先判断left<right，防止越界，下同 12. while (left<right && arr[right]>=arr[keyi]) //找小 13. { 14. right--; 15. } 16. 17. while (left < right && arr[left] <= arr[keyi]) //找大 18. { 19. left++; 20. } 21. 22. Swap(&arr[left], &arr[right]); //交换 23. } 24. 25. Swap(&arr[keyi], &arr[left]); 26. keyi = left; 27. 28. QuickSort(arr, begain, keyi-1); //递归左子列 29. QuickSort(arr, keyi+1, end); //递归右子列 30. }
三.挖坑法
动态演示
上面的Hoare法有很多坑，一不注意就容易写错，而挖坑法就没那么多坑了。
这个方法需要定义一个坑变量（hole），前面的Hoare法是交换两个元素，挖坑法是把值赋给坑位，然后更新一下坑位 。
1. void QuickSort(int* arr, int left, int right) 2. { 3. 4. if (left >= right) 5. return; 6. int begain = left; 7. int end = right; 8. int keyi = left; 9. int hole = left; //坑变量 10. while (left < right) 11. { 12. while (left < right && arr[right] >= arr[leyi]) //找小 13. { 14. right--; 15. } 16. arr[hole] = arr[right]; //赋值给坑位 17. hole = right; //更新坑位 18. while (left < right && arr[left] <= arr[keyi]) //找大 19. { 20. left++; 21. } 22. 23. arr[hole] = arr[left]; 24. hole = left; 25. } 26. 27. arr[hole] = key; 28. keyi = left; 29. //递归左右子列 30. QuickSort(arr, begain, hole - 1); 31. QuickSort(arr, hole + 1, end); 32. }
四.前后指针法
动态演示
这个方法可以说是实现快速排序最常用的方法了。
1.定义一个prev和cur，它们都表示数组的下标，当然你定义成指针也没问题，这里以下标为例；
2.cur=prev+1
注意：
a.prev要么紧跟着cur，即prev的下一个就是cur；
b.prev跟cur中间隔着比key大的一段值区间；
3.cur找到比key小的值，prev++，cur和prev位置互换，cur++；
4.cur找到比key大的值，cur++；
5.当cur>right时结束循环。
1. void QuickSort(int* arr, int left, int right) 2. { 3. if (left >= right) 4. return; 5. int begin = left, end = right; 6. int prev = left, cur = left + 1; 7. 8. int keyi = left; 9. while (cur <= right) 10. { 11. if (arr[cur] < arr[keyi]) 12. { 13. prev++; 14. Swap(&arr[cur], &arr[prev]); 15. cur++; 16. } 17. 18. while (arr[cur] > arr[keyi]) 19. { 20. cur++; 21. } 22. } 23. Swap(&arr[keyi], &arr[prev]); 24. keyi = prev; 25. QuickSort(arr, begin, keyi - 1); 26. QuickSort(arr, keyi + 1, end); 27. }
五.快速排序优化
在面对有序或是接近有序的情况下，快速排序的效率不高，是O(N^2)，那要怎么解决这个问题呢？
既然对有序或是接近有序的不行，那我们就打乱它的顺序，这里有两种方法：
1.通过生成区间内的随机下标，让keyi与randi的数据交换，这样就打乱了原来的顺序；
2.三路取中法。
随机下标交换法
1. int randi = left + rand() % (right - left); //随机key 2. Swap(&arr[keyi], &arr[randi]);
三路取中法
1. int GetMid(Sdatatype* arr, int left, int right) 2. { 3. int mid = (left + right) / 2; 4. if (arr[left] < arr[mid]) 5. { 6. if (arr[mid] < arr[right]) 7. return mid; 8. else if (arr[right] < arr[left]) 9. return left; 10. else 11. return right; 12. } 13. else //arr[left]>arr[mid] 14. { 15. if (arr[right] < arr[mid]) 16. return mid; 17. else if (arr[right] > arr[left]) 18. return left; 19. else 20. return right; 21. 22. } 23. 24. } 25. 26. if (left != midi) 27. Swap(&arr[left], &arr[midi]);
六.快速排序的特性
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
🐬🤖本篇文章到此就结束了，若有错误或是建议的话，欢迎小伙伴们指出；🕊️👻
😄😆希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；🥰🤩
😍😁谢谢你的阅读。😸😼
