排序--快速排序(附程序流程图)-Toy模板网

这篇具有很好参考价值的文章主要介绍了排序--快速排序(附程序流程图)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

概述

算法思路

大致步骤

过程图解

程序流程图

完整代码

概述

快速排序是对冒泡排序的一种改进。其核心思想是分治法，分而治之。最优时间复杂度是O(nlogn)。最坏时间复杂度是O(n^2)。

算法思路

先从数列中取出一个基准数(一般情况下我们取左边第一个数)，通过一趟排序将要排序的数列划分为独立的两个部分，要求是一趟排序完成后，基准数的左边的数都小于基准数，基准数的右边的数都大于基准数。然后按照此方法对这两部分数列分别进行快速排序，整个排序过程用递归进行，直至整个数变成有序数列。

大致步骤

从数列中取出一个数作为基准数；
把所有小于基准数的全部挪到左边，把所有大于基准数的挪到右边；
对基准数左右两部分分别重复步骤(1)和(2)。

过程图解

快速排序算法流程图,排序算法,数据结构,算法,c语言,流程图

程序流程图

快速排序算法流程图,排序算法,数据结构,算法,c语言,流程图

注：变量pos为基准数文章来源地址https://www.toymoban.com/news/detail-520307.html

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void qSort(int left,int right,int *arr) {
	if (left >= right) return;
	int i = left;
	int j = right;
	int pos = arr[i];        //确定基准数pos

	while (i<j) {

		while (i < j && arr[j] >= pos)
			j--;
		arr[i] = arr[j];
		while (i < j && arr[i] <= pos)
			i++;
		arr[j] = arr[i];

	}

	arr[i] = pos;

	qSort(left,i-1,arr);
	qSort(i+1,right,arr);
}

int main() {

	int i = 0;
	int sz = 0;
	int arr[50] = { 0 };
	do {

		scanf("%d",&arr[i++]);
		sz++;                    //sz作用：统计数列的个数

	} while (getchar()!='\n');

	qSort(0,sz-1,arr);


	for (int i = 0; i < sz;i++) {

		printf("%d ",arr[i]);

	}

	return 0;
}

到了这里，关于排序--快速排序(附程序流程图)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！