常用且强大的排序算法——快速排序

快速排序：

快速排序是交换排序的一种，是由冒泡排序改进而得的。

大家回忆一下，在冒泡排序中，只是简单的对相邻的两个记录进行比较，这是冒泡排序的专属限定，但就是这种限定限制了冒泡排序的能力

它每次交换只能消除一个逆序

那么有没有一种算法,一次比较可以消除多个逆序呢？

of course！那就是——快速排序

算法思维：

1.在待排序的n个数中取第一个数（当然可以使任意一个数）作为枢轴

2.用temp来记录这个数

3.进过一趟排序后，把所有小于temp的数交换到前面，把所有大于temp的数交换到后面

4.把以temp为界的左右两边分成两个子表，再对着两个子表进行123这三步，直到每个子表长度为1，排序结束~

图片展示：

具体步骤：

1.选定数组的第一个数作为枢轴，用temp来记录它

2.设置两个指针——low和high，分别指向a[0]和a[n-1]（数组末尾）

3.先从high的位置向左边开始搜索，找到第一个数值比temp小的数，此时high指向它，将这个数换到low所指向的位置，high停止移动

4.再从low开始向右边开始搜索，找到第一个数值比temp大的数，此时low指向它，将这个数换到high所指向的位置，low停止移动

5.接着进行34的循环，直到low和high重合，将temp的值赋值给low（或者high）

6.345就是一趟排序，对temp的左右两边进行拆分成两个子表，再次进行345，直到数组的每个子表的长度都是1，快速排序结束

核心代码：

找位置部分：

快速排序部分：

总代码：

#include<iostream>
using namespace std;
//找位置
int Partition(int a[], int low,int high) {
  int temp = a[low];
  while (low < high) {
    while (low < high && a[high] >= temp)
      high--;
    a[low] = a[high];
    while (low < high && a[low] < temp)
      low++;
    a[high] = a[low];
  }
  a[low] = temp;
  return low;
}
//快速排序
void QuickSort(int a[], int low, int high) {
  if (low < high) {//长度要大于一
    //找枢轴
    int mid = Partition(a, low, high);
    //分别递归的搜索左右子表
    QuickSort(a, low, mid - 1);
    QuickSort(a, mid + 1, high);
  }
}
//展示函数
void display(int a[], int n) {
  for (int i = 0; i < n; i++)
    cout << a[i] << "  ";
}
int main()
{
  int n;
  cin >> n;
  int* a = new int[n];
  for (int i = 0; i < n; i++)
    cin >> a[i];
  QuickSort(a, 0, n - 1);
  display(a, n);
  cout << endl;
  system("pause");
  return 0;
}

测试结果：

复杂度分析：

• 时间复杂度：

最好情况:O(nlog₂n)

最坏情况:O(n²)

平均情况:O(nlog₂n)

• 空间复杂度：

快速排序是递归的，执行时需要有一个栈来存放数据

空间复杂度:O(log₂n)

• 稳定性：

记录非顺次的移动导致排序方法是不稳定的

• 特点：

1.排序的过程由于需要定位，所以适用于顺序存储结构，不适用于链式存储结构

2.当n较大时，在平均情况下，快速排序是所有内部排序中速度最快的一种

PS:这就是快速排序的全部内容了，点个赞再走吧~