admin管理员组

文章数量:815885

快速排序算法的C++实现

目录

  • 算法描述
  • 算法执行过程
  • 算法实现
  • 算法执行结果
  • 算法性能分析
  • 参考

算法描述

快速排序又叫分区排序,它是一种平均性能非常好的排序方法。快速排序使用分治思想。这个算法优于归并算法,因为它在原位上排序,不需要辅助的存储空间。对一个数组A[p…r]进行排序一般有三个步骤。
分解:数组A[p…r]被划分为两个子数组A[p…q-1]和A[q+1…r],是的A[p…q-1]中的每一个元素都小于等于A[q],而A[q]也小于等于A[q+1…r]中的每个元素。同时计算下标q。
递归:通过递归调用快速排序,对子数组A[p…q-1]和A[q+1…r]进行排序。
合并:因为子数组都是原址排序的,所以不需要合并操作:数组A[p…r]已经有序。

算法执行过程

原始数组:49 38 65 97 76 13 27
选择第一个元素49作为枢轴
49 38 65 97 76 13 27 49
i          j
<1>
首先使j向左移动遇到比枢轴49小的元素或i与j相等时停下来
49 38 65 97 76 13 27 49
i          j
这时,将j所指向的27覆盖到i所指向的元素
27 38 65 97 76 13      49
i          j
<2>
变换方向,使i从前向后移动,遇到比枢轴49大的元素或i与j相等时停下来
27 38 65 97 76 13      49
    i      j
将65覆盖到j所指向的位置
27 38      97 76 13 65 49
    i      j
<3>
换方向,使j向左移动,遇到比枢轴49小的元素或i与j相等时停下来
27 38      97 76 13 65 49
    i    j
将13覆盖到i所指的位置
27 38 13 97 76      65 49
    i    j
<4>
换方向,使i向右移动,遇到比枢轴49大的元素或i与j相等时停下来
27 38 13 97 76      65 49
      i    j
将97覆盖到j所指向的位置
27 38 13      76 97 65 49
      i    j
<5>
换方向,遇到比枢轴49小的元素或i与j相等时停下来
27 38 13      76 97 65 49
      ij
当i与j相等时,此次扫描结束,此时i等于j的位置就是枢轴的最终位置,此时i指向的位置的左边都比49小,右边都比49大
27 38 13 49 76 97 65
      ij
<6>
此时分别对49左边的子序列和右边的子序列进行上述排序

算法实现

#include <iostream>
using namespace std;
void quickSort(int a[], int low, int high)
{int temp;int i = low, j = high;if (low < high){temp = a[low];while (i < j){while (j > i&&a[j] >= temp)--j;if (i < j){a[i] = a[j];++i;}while (i < j&&a[i] < temp)++i;if (i < j){a[j] = a[i];--j;}}a[i] = temp;for (int k = 0; k < 7; k++){if(k!=i)cout << a[k] << " ";elsecout <<"<"<< a[k] <<">"<< " ";}cout << endl;quickSort(a, low, i - 1);quickSort(a, i + 1, high);}
}
int main()
{int arr[] = { 49,38,65,97,76,13,27 };cout << "排序之前数组为: ";for (int k = 0; k < 7; k++){cout << arr[k] << " ";}cout << endl;cout << "中间的每个步骤" << endl;quickSort(arr, 0, 6);cout << "排序之后数组为: ";for (int k = 0; k < 7; k++){cout << arr[k] << " ";}cout << endl;system("pause");return 0;
}

算法执行结果

算法性能分析

快速排序算法的性能如表所示,当数据有序时,以第一个关键字为基准分为两个子序列,前一个子序列为空,此时执行效率最差。相反,当数据接近无序时,算法执行效率最好。

平均时间复杂度最坏情况最好情况空间复杂度稳定性
O(n㏒₂ⁿ)O(n2)O(n㏒₂ⁿ)O(n㏒₂ⁿ)不稳定

参考

Algorithms (Fourth Edition) [美] Robert Sedgewick
数据结构高分笔记 率辉

本文标签: 快速排序算法的C实现