快速排序

基本思想

  • 分治：在未排序序列中选择一个基准数（一般为第一个），将小于基准数的放在其左边，大于基准数的放在其右边，即分成两个区间
  • 递归：将上述两个区间，每个区间内执行上述操作，以此类推，直到排序完成

步骤

  • 选择一个基准数，一般为第一个: pivot := list[left]
  • 将小于基准数的放在其左边
  • 将大于基准数的放在其右边
  • 对每个分区执行递归操作：quickSort(list, left, i-1)；quickSort(list, i+1, right)

By C++

  1. #include <stdio.h>
  2. #define MaxSize 100
  4. typedef int KeyType;        /*关键字类型*/
  6. typedef char ElemType[10];    /*其他数据项类型*/
  8. typedef struct 
  9. {    
  10.     KeyType key;               /*关键字域*/
  11.     ElemType data;             /*其他数据域*/
  12. } LineList;                    /*线性表元素类型*/
  14. void QuickSort(LineList R[],int s,int t) /*对R[s]至R[t]的元素进行快速排序*/
  15. {
  16.     int i=s,j=t;
  17.     LineList tmp;
  18.     if (s<t)                 /*区间内至少存在一个元素的情况*/
  19.     {    tmp=R[s];             /*用区间的第1个记录作为基准*/
  20.         while (i!=j)          /*从区间两端交替向中间扫描,直至i=j为止*/
  21.         {    while (j>i && R[j].key>tmp.key) 
  22.                 j--;          /*从右向左扫描,找第1个关键字小于tmp.key的R[j]*/ 
  23.             R[i]=R[j];        /*找到这样的R[j],则R[i]和R[j]交换*/
  24.             while (i<j && R[i].key<tmp.key) 
  25.                 i++;        /*从左向右扫描,找第1个关键字大于tmp.key的R[i]*/
  26.             R[j]=R[i];        /*找到这样的R[i],则R[i]和R[j]交换*/
  27.         }
  28.         R[i]=tmp;
  29.         QuickSort(R,s,i-1);    /*对左区间递归排序*/
  30.         QuickSort(R,i+1,t);    /*对右区间递归排序*/
  31.     }
  32. }
  34. void main()
  35. {
  36.     LineList R[MaxSize];
  37.     KeyType a[]={75,87,68,92,88,61,77,96,80,72};
  38.     int n=10,i;
  39.     for (i=0;i<n;i++)
  40.         R[i].key=a[i];
  41.     printf("排序前:");
  42.     for (i=0;i<n;i++)
  43.         printf("%3d",R[i].key);
  44.     printf("\n");
  45.     QuickSort(R,0,n-1);
  46.     printf("排序后:");
  47.     for (i=0;i<n;i++)
  48.         printf("%3d",R[i].key);
  49.     printf("\n");
  50. }

By Golang

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. func quickSort(list []int, left, right int) []int {
  8.     if left < right {
  9.         i, j := left, right
  10.         pivot := list[left] // 以左边第一个数作为基准数，将第一个数暂存在pivot变量中
  12.         // 分治
  13.         for i < j {
  14.             // 从右向左找出第一个小于基准数的，将list[j]赋值给list[i] 
  15.             for j > i && list[j] > pivot {
  16.                 j--
  17.             }
  18.             list[i] = list[j]
  20.             // 从左向右找出第一个大于基准数的，将list[i]赋值给list[j] 
  21.             for i < j && list[i] < pivot {
  22.                 i++
  23.             }
  24.             list[j] = list[i]
  25.         }
  26.         list[i] = pivot
  27.         fmt.Println(list) // 打印该趟的序列
  29.         // 递归
  30.         quickSort(list, left, i-1)
  31.         quickSort(list, i+1, right)
  32.     }
  33.     return list
  34. }
  36. func main() {
  37.     list := []int{75, 87, 68, 92, 88, 61, 77, 96, 80, 72}
  38.     fmt.Println("初始序列:", list)
  39.     result := quickSort(list, 0, len(list)-1)
  40.     fmt.Println("最终结果:", result)
  41. }

排序过程

  1. 初始序列: [75 87 68 92 88 61 77 96 80 72]
  3. 第 1 趟：[72 61 68 75 88 92 77 96 80 87]
  4. 第 2 趟：[68 61 72 75 88 92 77 96 80 87]
  5. 第 3 趟：[61 68 72 75 88 92 77 96 80 87]
  6. 第 4 趟：[61 68 72 75 87 80 77 88 96 92]
  7. 第 5 趟：[61 68 72 75 77 80 87 88 96 92]
  8. 第 6 趟：[61 68 72 75 77 80 87 88 96 92]
  9. 第 7 趟：[61 68 72 75 77 80 87 88 92 96]
  11. 最终结果: [61 68 72 75 77 80 87 88 92 96]