推荐视频：郝斌数据结构之快速排序

1. 算法思想

从数组中选择一个元素，将这个元素称为中轴元素，然后把数组中所有小于中轴元素的元素放在其左边，将所有大于或等于中轴元素的元素放在其右边。显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素起，把大数组切割成两个小数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和中轴元素右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

2. 简单概述

平均时间复杂度： O(n * log n)
最好情况： O(n * log n)
最坏情况：O(n * n)
排序方式：原地排序
稳定性：非稳定
空间复杂度： O(log n)

3. 算法步骤

1. 选取第一个数为基准；
2. 将比基准小的数交换到前面，比基准大的数交换到后面；
3. 对左右区间重复第二步，直到各区间只有一个数。

4. 代码实现

4.1 普通数组实现（C++）

#include<iostream>
using namespace std;//函数声明
void quickSort(int*, int, int);
int findPos(int*, int, int);int main()
{int nums[6] = { 2, -3, 9, 5, 7, 8 };//第二个参数：第一个元素的下标  第三个参数：最后一个元素的下标 quickSort(nums, 0, 5);for (int i = 0; i < 6; ++i){cout << nums[i] << " ";}cout << endl;system("pause"); //按任意键继续return 0;
}void quickSort(int* nums, int low, int high)
{int pos;if (low < high){pos = findPos(nums, low, high);quickSort(nums, low, pos - 1);quickSort(nums, pos + 1, high);}
}int findPos(int* nums, int low, int high)
{int val = nums[low];while (low < high){while (low < high && nums[high] >= val)--high;nums[low] = nums[high];while (low < high && nums[low] <= val)++low;nums[high] = nums[low];}nums[low] = val;return low; //low和high都行，因为此时low == high
}

4.2 vector容器实现（C++）

#include<iostream>
#include<vector>
using namespace std;void printVector(vector<int>& nums) 
{for (auto a : nums)cout << a << " ";cout << endl;
}
void quickSort(vector<int>& nums, int begin, int end) 
{if (begin >= end) return;int low = begin, high = end, val = nums[begin];while (low < high) {while (low < high && nums[high] >= val) --high;nums[low] = nums[high];while (low < high && nums[low] <= val)++low;nums[high] = nums[low];}nums[low] = val;quickSort(nums, begin, low - 1); // 前半递归quickSort(nums, low + 1, end); // 后半递归
}int main()
{vector<int>nums = { 9,-5,4,10,6,5,7,22 };quickSort(nums, 0, nums.size() - 1);printVector(nums);system("pause"); //按任意键继续return 0;
}

4.3 C语言版

#include<stdio.h>void quickSort(int * a, int low, int high);
int findPos(int * a, int low, int high);int main()
{int a[6] = {2, 1, 33, 5, 4, 3};int i; //第二个参数：第一个元素的下标  第三个参数：最后一个元素的下标 quickSort(a, 0, 5);for(i = 0; i < 6; ++i){printf("%d ", a[i]);}printf("\\n");return 0;
}void quickSort(int * a, int low, int high)
{int pos;if(low < high){pos = findPos(a, low, high);quickSort(a, low, pos - 1);quickSort(a, pos + 1, high);}
}int findPos(int * a, int low, int high)
{int val = a[low];while(low < high){while(low < high && a[high] >= val)--high;a[low] = a[high];while(low < high && a[low] <= val)++low;a[high] = a[low];	}a[low] = val;return low; //low和high都行 
}

5. 补充知识

• 稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序；

• 非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

• 原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序；

• 非原地排序：需要利用额外的数组来辅助排序。

• 时间复杂度：一个算法执行所消耗的时间（次数，因为同一程序在不同系统的执行时间可能不同）；

• 空间复杂度：运行完一个算法所需的内存大小。

• 十大排序中的稳定排序：

  • 冒泡排序（bubble sort） — O(n * n)
  • 插入排序 （insertion sort）— O(n * n)
  • 归并排序 （merge sort）— O(n * log n)

• 十大排序中的非稳定排序：（面试考察中一般问快排，选择，希尔，堆这几种非稳定排序）

  • 选择排序 （selection sort）— O(n * n)
  • 希尔排序 （shell sort）— O(n * log n)
  • 堆排序 （heapsort）— O(n * log n)
  • 快速排序 （quicksort）— O(n * log n)

6. 其它排序算法

1. 冒泡排序
2. 选择排序
3. 快速排序
4. 插入排序
5. 希尔排序
6. 归并排序
7. 堆排序
8. 计数排序
9. 桶排序
10. 基数排序