900字范文 > 排序算法 | 快速排序算法的图解实现复杂度和稳定性分析与优化

排序算法 | 快速排序算法的图解实现复杂度和稳定性分析与优化

时间：2021-12-18 00:31:35

今天讲解一下快速排序算法的原理以及实现、复杂度和稳定性分析与优化

1 快速排序的原理

快速排序是所有内部排序算法中平均性能最优的排序算法

快速排序是对冒泡排序算法的一种改进

快速排序由C. A. R. Hoare在1960年提出。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

快速排序的基本思想是基于分治法的

在待排序表L[1…n]中任取一个元素pivot作为枢轴(或基准，通常取首元素)

也就是常见的固定位置选取基准

通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和L[k+1…n]

使得L[1…k-1]中的所有元素小于pivot

L[k+1.n]中的所有元素大于等于pivot

则pivot放在了其最终位置L(k)上

这个过程称为一趟快速排序(或一次划分)

然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

一趟快速排序的过程是一个交替搜索和交换的过程

常见方法就是挖坑法

不过需要注意：

如果选择第一个数组元素为基准时，必须先从后向前进行

如果选择最后一个数组元素为基准时，必须先从前向后进行

挖坑法的流程：

2 快速排序代码实现

首先写好划分操作算法，然后递归调用~

// 每一次的划分操作int Partition(int *arr, int left, int right){int i = left;int j = right;// 固定位置选取基准选第一个 int k = arr[left]; while (i < j){while(i < j && arr[j] >= k) {j--;}arr[i] = arr[j];while(i < j && arr[i] <= k) {i++;}arr[j] = arr[i];}arr[i] = k;return i;}// 递归调用实现快速排序void QuickSort(int *arr,int low,int high){int k = Partition(arr,low,high);if(low < k-1){QuickSort(arr,low,k-1);}if(high > k+1){QuickSort(arr,k+1,high);}}

示例：

int arr[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};