当前位置:   article > 正文

排序算法之快速排序(java、python和C++实现)_python现有如下代码: try: print(count) demo_list = ["pyth

python现有如下代码: try: print(count) demo_list = ["python", "java", "c", "c

快速排序的基本思想

快速排序是对起泡排序(冒泡排序)的改进,采用分治思想。在各种排序方法中,快速排序比较次数较少,速度较快。

给出一组待排序的数据记录。我们需要选择一个基准值作为分区标准,通常我们取第一个记录或者最后一个记录作为基准值。然后再将所有小于该基准值的记录移到左边,将所有大于该基准值得记录移到右边,中间放基准值记录,称为一趟排序。接着,对左右两个子序列分别重复上述过程。继续下去,直到所有的记录都排好序。

算法原理

例题:

待排序的数组:{5,7,2,9,1,4,6,8,10,3}

期望排好序后的数组:{1,2,3,4,5,6,7,8,9,10}

例题解析:

第一步:选择数组的第一个数据作为基准值,即 5

第二步:首先从左边开始,也就是从第二个数据开始与基准值比较。若小于基准值,则继续比较下一条数据;若大于基准值,则停止比较,并记录下大于基准值的数据的索引(下标)

第三步:从最右边的数据与比较起,若大于基准值,则继续比较下一条数据;若小于基准值,则停止比较,并记录下小于基准值的数据的索引(下标)

第四步:将左边大于基准值的数据与右边小于基准值的数据交换。

第五步:重复第二、三、四步,直到将数组中所有数据比较完。这时需要将第一个数据也就是基准值交换到左右分好的序列中间来。这时数组分成两边,左边的数据都小于基准,右边的数据都大于基准值。

第六步:将左右两边的数据分别重复以上五个步骤,直到所有数据排好序。注意,接下来的每一趟排序不是以5作为基准值了,而是以左右两边的数据的第一个数据作为基准值。

例题数组的每一趟排序的结果:

【】内是下一趟要比较的序列

第一趟后:{【1,3,2,4】,5,【9,6,8,10,7】}

第二趟后:{1,【3,2,4】,5,9,6,8,10,7}

第三趟后:{1,2,3,4,5,【9,6,8,10,7】 }

第四趟后:{1,2,3,4,5,【7,6,8】,9,【10】 }

第五趟后:{1,2,3,4,5,【6 】,7,【 8 】,9,10 }


java实现的代码:

  1. public class QuickSort {
  2. public static void main(String[] args) {
  3. //要进行排序的数组
  4. int[] a = {5,7,2,9,1,4,6,8,10,3};
  5. //将数组a从小到大排序
  6. quickSort(a, 0, a.length-1);
  7. //打印数组
  8. printArray(a);
  9. }
  10. /**
  11. * 快速排序
  12. * 将数组a的某一段元素进行划分,小的在左边,大的在右边
  13. * @param a
  14. * @param left
  15. * @param right
  16. */
  17. private static void quickSort(int[] a, int left, int right) {
  18. //如果只有一个元素,就不用再排下去了
  19. if(left < right){
  20. int pivot = a[left]; //用序列最左边的记录作为基准值
  21. int i = left, j = right;
  22. while(i < j){
  23. //从左边开始遍历,如果比基准值小,就继续向右走
  24. while(i < j && a[i] <= pivot) i++;
  25. //从右边开始遍历,如果比基准值大,就继续向左走
  26. while(i < j && a[j] > pivot) j--;
  27. //上面的while循环结束时,就说明当前的a[i]的值比基准值大,
  28. //当前的a[j]的值比基准值小,a[i]应与a[j]互换
  29. if(i < j){
  30. swap(a, i, j);
  31. }
  32. }
  33. //分组结束后,要将基准值交换到两组之间
  34. swap(a, left, i-1);
  35. //继续递归排序左边的序列
  36. quickSort(a, left, i-2);
  37. //继续递归排序右边的序列
  38. quickSort(a, i, right);
  39. }
  40. }
  41. /**
  42. * 交换数组a中索引为 i 和 j 之间的数值
  43. * @param a
  44. * @param i
  45. * @param j
  46. */
  47. private static void swap(int[] a, int i, int j) {
  48. int temp = a[i];
  49. a[i] = a[j];
  50. a[j] = temp;
  51. }
  52. //打印数组
  53. private static void printArray(int[] a) {
  54. for(int i = 0;i < a.length;i++){
  55. System.out.print(a[i] + " ");
  56. }
  57. }
  58. }

python实现的代码:

  1. def quickSort(a, l, r):
  2. if l < r:
  3. pivot = a[l]
  4. i = l
  5. j = r
  6. while i < j:
  7. while i < j and a[i] <= pivot:
  8. i += 1
  9. while i < j and a[j] > pivot:
  10. j -= 1
  11. if i < j:
  12. swap(a, i, j)
  13. swap(a, l, i-1)
  14. quickSort(a, l, i-2)
  15. quickSort(a, i, r)
  16. def swap(a,i,j):
  17. temp = a[i]
  18. a[i] = a[j]
  19. a[j] = temp
  20. a = [5,7,2,9,1,4,6,8,10,3]
  21. quickSort(a,0,len(a)-1)
  22. print(a)


C++实现的代码与java的代码基本一样,只需要修改极少的部分:

  1. #include <iostream>
  2. using namespace std;
  3. /**
  4. * 交换数组a中索引为 i 和 j 之间的数值
  5. * @param a
  6. * @param i
  7. * @param j
  8. */
  9. void swap(int a[], int i, int j)
  10. {
  11. if(i != j)
  12. {
  13. int temp = a[i];
  14. a[i] = a[j];
  15. a[j] = temp;
  16. }
  17. }
  18. //打印数组
  19. void printArray(int a[], int len)
  20. {
  21. for(int i = 0;i < len;i++)
  22. {
  23. cout<<a[i]<<" ";
  24. }
  25. }
  26. void quickSort(int a[], int left, int right) {
  27. //如果只有一个元素,就不用再排下去了
  28. if(left < right){
  29. int pivot = a[left]; //用序列最左边的记录作为基准值
  30. int i = left, j = right;
  31. while(i < j){
  32. //从左边开始遍历,如果比基准值小,就继续向右走
  33. while(i < j && a[i] <= pivot) i++;
  34. //从右边开始遍历,如果比基准值大,就继续向左走
  35. while(i < j && a[j] > pivot) j--;
  36. //上面的while循环结束时,就说明当前的a[i]的值比基准值大,
  37. //当前的a[j]的值比基准值小,a[i]应与a[j]互换
  38. if(i < j){
  39. swap(a, i, j);
  40. }
  41. }
  42. //分组结束后,要将基准值交换到两组之间
  43. swap(a, left, i-1);
  44. //继续递归排序左边的序列
  45. quickSort(a, left, i-2);
  46. //继续递归排序右边的序列
  47. quickSort(a, i, right);
  48. }
  49. }
  50. int main(int argc, char* argv[])
  51. {
  52. int a[] = {5,7,2,9,1,4,6,8,10,3};
  53. int len = sizeof(a)/sizeof(int);
  54. quickSort(a, 0 , len-1);
  55. printArray(a, len);
  56. return 0;
  57. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/449244
推荐阅读
相关标签
  

闽ICP备14008679号