网站做任务包括什么,做同城网站需要哪些,网站建设内容模板下载,做网站公司排名文章参考十大经典排序算法-快速排序算法详解进行整理补充。快速排序是最快的排序方法。 排序思路#xff1a;分治法-挖坑填数#xff1a;大问题分解为各个小问题#xff0c;对小问题求解#xff0c;使得大问题得以解决 文章目录 1. 什么是快速排序1.1 概念1.2 算法原理1.3 …文章参考十大经典排序算法-快速排序算法详解进行整理补充。快速排序是最快的排序方法。 排序思路分治法-挖坑填数大问题分解为各个小问题对小问题求解使得大问题得以解决 文章目录 1. 什么是快速排序1.1 概念1.2 算法原理1.3 算法实现1.3.1 核心代码1.3.2 整体代码 2. 快速排序算法特点2.1 时间复杂度2.2 空间复杂度2.3 稳定性 1. 什么是快速排序
1.1 概念
快速排序Quick Sort是从冒泡排序算法演变而来的实际上是在冒泡排序基础上的递归分治法。快速排序在每一轮挑选一个基准元素并让其他比它大的元素移动到数列一边比它小的元素移动到数列的另一边从而把数列拆解成了两个部分。
1.2 算法原理
这是一个无序数列4、5、8、1、7、2、6、3我们要将它按从小到大排序。按照快速排序的思想我们先选择一个基准元素进行排序。 我们选取4为我们的基准元素并设置基准元素的位置为index(可以看做一个坑位比较后满足条件的就填进去)设置两个指针left和right分别指向最左和最右两个元素 接着从right指针开始把指针所指向的元素和基准元素做比较如果比基准元素大则right指针向左移动如果比基准元素小则把right所指向的元素填入index中
3和4比较3比4小将3填入index中原来3的位置成为了新的index同时left右移一位 然后我们切换left指针进行比较如果left指向的元素小于基准元素则left指针向右移动如果元素大于基准元素则把left指向的元素填入index中
5和4比较5比4大将5填入index中原来5的位置成为了新的index同时right左移一位 接下来我们再切换到right指针进行比较6和4比较6比4大right指针左移一位 2和4比较2比4小将2填入index中原来2的位置成为新的indexleft右移一位 随着left右移right左移最终left和right重合 此时我们将基准元素填入index中这时基准元素左边的都比基准元素小右边的都比基准元素大这一轮交换结束 第一轮基准元素4将序列分成了两部分左边小于4右边大于4第二轮则是对拆分后的两部分进行比较
此时我们有两个序列需要比较分别是3、2、1和7、8、6、5重新选择左边序列的基准元素为3右边序列的基准元素为7 第二轮排序结束后结果如下所示 此时3、4、7为前两轮的基准元素是有序的7的右边只有8一个元素也是有序的因此第三轮我们只需要对1、2和5、6这两个序列进行排序 第三轮排序结果如下所示 至此所有的元素都是有序的.
1.3 算法实现
1.3.1 核心代码
//快速排序 升序
void quick_sort(int arr[], int start, int end)
{int i start;int j end;int temp arr[start];//基准数if (i j){while (i j){//从右往左找比基准数小的while (i j arr[j] temp){j--;}//填坑if (i j){arr[i] arr[j];i;}//从左向右找比基准数大的数while (i j arr[i] temp){i;}//填坑if (i j){arr[j] arr[i];j--;}}//基准数放入ij中arr[i] temp;//对基准数左半部分快速排序quick_sort(arr, start, i - 1);//对基准数右半部分快速排序quick_sort(arr, j 1, end);}}1.3.2 整体代码
#include iostream
using namespace std;void swap(int* a, int* b)
{int temp *a;*a *b;*b temp;
}//打印数组
void printArr(int arr[])
{for (int i 0; i 10; i){cout arr[i] endl;}
}//快速排序 升序
void quick_sort(int arr[], int start, int end)
{int i start;int j end;int temp arr[start];//基准数if (i j){while (i j){//从右往左找比基准数小的while (i j arr[j] temp){j--;}//填坑if (i j){arr[i] arr[j];i;}//从左向右找比基准数大的数while (i j arr[i] temp){i;}//填坑if (i j){arr[j] arr[i];j--;}}//基准数放入ij中arr[i] temp;//对基准数左半部分快速排序quick_sort(arr, start, i - 1);//对基准数右半部分快速排序quick_sort(arr, j 1, end);}}int main()
{int arr[] { 8,2,3,9,6,4,7,1,5,10 };quick_sort(arr,0,9);printArr(arr);system(pause);return 0;
}运行结果
2. 快速排序算法特点
2.1 时间复杂度
快速排序算法在分治法的思想下原数列在每一轮被拆分成两部分每一部分在下一轮又分别被拆分成两部分直到不可再分为止平均情况下需要logn轮因此快速排序算法的平均时间复杂度是O(nlogn)
在极端情况下快速排序算法每一轮只确定基准元素的位置时间复杂度为O(N^2)
2.2 空间复杂度
快速排序算法排序过程中只是使用数组原本的空间进行排序因此空间复杂度为O(1)
2.3 稳定性
快速排序算法在排序过程中可能使相同元素的前后顺序发生改变所以快速排序是一种不稳定排序算法
快速排序1快速排序2参考博文常见的几种排序C
