【算法】快速排序

目录

核心思想：

过程：

演示：

第一趟：

第二趟：

 代码：

---

核心思想：

从待排序列中取一个元素作为中心，所有比它小或相等的元素一律放在前面，

所有比它大的元素放在后面，形成左右两个表，然后在对各个子表重新选择

中心元素，并按此规则调整，直到每一个子表的元素只剩最后一个，此时

便成为有序序列了。

过程：

设置两个指针 i 和 j ，分别从左往右找比基准元素大的和从右往左找比基准元素小

的元素

演示：

待排序序列：（ 2   8   7  1   3    5     6     4）

选则关键字：   4      （以4为基准）

第一趟：

2和4进行比较，2小于4 不交换位置，指针 i 向右移动一位

8和4比较，8大于4，交换位置

此时，基准元素4左边元素都比4小，移动  j 指针向左移动一位

6与4比较，6大于4，不交换位置，指针 j 向左移动一位

 

5与4比较，5大于4，位置不交换，指针 j 向左移动一位

3与4比较，3小于4，交换位置

此时，基准元素4的右边元素都比4大，移动 i 指针向右移动一位

 7和4比较，7大于4，交换位置

 此时，基准元素4左边元素小于4，移动 j 指针向左移动一位

1与4比较，1小于4，交换位置

此时，基准元素4的左边元素都比4小，右边元素都比4大，至此第一趟排序结束

第二趟：

此时划分两个部分，第一部分（2 3 1）  第二部分 （7 5 6 8）

分别按照上述方法进行排列

最后结果 1 2 3  4   5   6   7   8  9 

 代码：

#include <stdio.h>// 定义数组长度
#define N 10// 快速排序函数
void quick_sort(int arr[], int left, int right)
{if (left < right) {int i = left, j = right, pivot = arr[left];while (i < j) {while (i < j && arr[j] >= pivot) {j--;}if (i < j) {arr[i++] = arr[j];}while (i < j && arr[i] <= pivot) {i++;}if (i < j) {arr[j--] = arr[i];}}arr[i] = pivot;quick_sort(arr, left, i - 1);quick_sort(arr, i + 1, right);}
}// 主函数
int main()
{int arr[N] = {5, 9, 3, 6, 1, 8, 2, 7, 4, 0};quick_sort(arr, 0, N - 1);for (int i = 0; i < N; i++) {printf("%d ", arr[i]);}return 0;
}