• 快速排序
    • 基本思想
    • 步骤
    • By C++
    • By Golang
    • 排序过程

    快速排序

    基本思想

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

    步骤

    • 选择一个基准数，一般为第一个: 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]