快速排序 | C++|时间空间复杂度

1.概念

快速排序(QuickSort)的基本思想是:通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

2.算法思想描述

1.进行一次划分：找一个基准(枢轴)，经过一趟遍历从后往前找比基准小的记录，找到往前移，然后从前往后找比基准大的记录，找到往后移，直到以基准为中枢，将序列分为两部分，即基准左边的记录都小于基准右边的记录。

2.不断的将序列分为两部分，分别对子序列进行一份划分，直到序列不可在划分，达到整个序列有序。

一次划分的思想：

3.代码

#include<iostream>
using namespace std;
int Partition(int* arr, int low, int high)//O(n)
{int pivot = arr[low];//用子序列的第一个记录作为基准(枢轴)while (low < high)//从序列的两端交替向中间扫描{//从后往前找比基准小的记录，找到往前移while (low < high && arr[high] >= pivot) high--;if (low < high){arr[low++] = arr[high];}//从前往后找比基准大的记录，找到往后移while (low < high && arr[low] <= pivot) low++;if (low < high){arr[high--] = arr[low];}}arr[low] = pivot;//经过一次划分，将基准数字放在他该在的位置上(即基准左边的记录都小于基准右边的记录)return low;//返回基准(枢轴)所在的位置
}void Quick(int* arr, int low, int high)//O(nlogn)
{if (low >= high) return;int pivot = Partition(arr, low, high);//将基准进行一次划分，序列分为两份Quick(arr, low, pivot - 1);//基准左边进行排序Quick(arr, pivot + 1, high);//基准右边进行排序
}void QuickSort(int* arr, int len)
{Quick(arr, 0, len - 1);
}void Show(int* arr, int len)
{for (int i = 0; i < len; i++){printf("%d ", arr[i]);}printf("\n");
}int main()
{int arr[] = { 9,3,12,6,7,10,5,8,21,4 };//待排序序列int len = sizeof(arr) / sizeof(arr[0]);QuickSort(arr, len);printf("快速排序结果为：");Show(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}