文档章节

【源码共享】快速排序算法的几种实现方式

Master_Li
 Master_Li
发布于 2016/10/08 13:37
字数 1763
阅读 332
收藏 0

快速排序算法的基本特性
时间复杂度:O(n*lgn)
最坏:O(n^2)
空间复杂度:O(n*lgn)
不稳定。

快速排序是一种排序算法,对包含n个数的输入数组,平均时间为O(nlgn),最坏情况是O(n^2)。
通常是用于排序的最佳选择。因为,基于比较的排序,最快也只能达到O(nlgn)。

在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

算法步骤:

  1. 从数列中挑出一个元素,称为 “基准”(pivot),

  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

首先简单描述下快速排序的基本思路

快速排序是基于分治模式处理的,对一个典型子数组A[p…r]排序的分治过程为三个步骤:

1.分解:

A[p..r]被划分为俩个(可能空)的子数组A[p ..q-1]和A[q+1 ..r],使得

A[p ..q-1] <= A[q] <= A[q+1 ..r]

2.解决:通过递归调用快速排序,对子数组A[p ..q-1]和A[q+1 ..r]排序。

3.合并。

实现代码如下

代码一:

#include <stdio.h>

// 一趟排序过程
int partition(int *arr, int low, int high)
{
	int pivot = arr[high];//选最右边元素为基准
	int i = low - 1;//j为游标,i为本趟排序后位置
	int j, tmp;

	for (j = low; j<high; ++j)//从左向右依次检查
	    if (arr[j]<pivot)
		{
		    tmp = arr[++i];
		    arr[i] = arr[j];
		    arr[j] = tmp;
	    }

	tmp = arr[i + 1];//将基准元素归位
	arr[i + 1] = arr[high];
	arr[high] = tmp;

	return i + 1;//返回基准元素的最终位置
}

//排序算法过程:分治思想,将左右两部分分别递归
void quick_sort(int *arr, int low, int high)
{
	if (low<high){
		int mid = partition(arr, low, high);
		quick_sort(arr, low, mid - 1);
		quick_sort(arr, mid + 1, high);
	}
}


int main()
{
	int arr[10] = { 1, 4, 6, 2, 5, 8, 7, 6, 9, 12 };//测试数据
	int i;
	quick_sort(arr, 0, 9);
	for (i = 0; i<10; ++i)
		printf("%d ", arr[i]);

	getchar();
}

排序结果:

代码二:

#include <stdio.h> 

int a[101], n;//定义全局变量,这两个变量需要在子函数中使用 

void quicksort(int left, int right)
{
	int i, j, t, temp;
	if (left>right)
		return;

	temp = a[left]; //temp中暂存基准数 
	i = left;
	j = right;
	while (i != j)
	{
		//顺序很重要,要先从右边开始找,找比基准数小的数值
		while (a[j] >= temp && i<j)
			j--;
		//再找左边的,找比基准数大的数值
		while (a[i] <= temp && i<j)
			i++;
		//交换两个数在数组中的位置 
		if (i<j)
		{
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	//最终将基准数归位 
	a[left] = a[i];
	a[i] = temp;

	quicksort(left, i - 1);//继续处理左边的,这里是一个递归的过程 
	quicksort(i + 1, right);//继续处理右边的 ,这里是一个递归的过程 
}

int main()
{
	int i;
	//读入数据 
	printf("please input the length of array sorted:");
	scanf_s("%d", &n);
	printf("please input the number of array element sorted:\n");
	for (i = 1; i <= n; i++)
		scanf_s("%d", &a[i]);
    //快速排序调用 
	quicksort(1, n);
	//输出排序后的结果 
	for (i = 1; i <= n; i++)
		printf("%d ", a[i]);

	getchar();//消除回车符
	getchar();//等待输入
	return 0;
}

排序结果:

代码三:本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序,然后再对整个基本有序序列用插入排序算法排序

#include<stdio.h>

void print(int a[], int n){
	for (int j = 0; j<n; j++){
		printf("%d  ",a[j]);
	}
	printf("\n");
	return;
}

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

// 一次排序过程
int partitions(int a[], int low, int high)
{
	int privotKey = a[low];					 //基准元素
	while (low < high)                       //从表的两端交替地向中间扫描
	{					    
		while (low < high  && a[high] >= privotKey) //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端
			--high; 
		swap(&a[low], &a[high]);
		while (low < high  && a[low] <= privotKey) 
			++low; 
		swap(&a[low], &a[high]);
	}
	print(a, 10);                            //输出每次排序结果
	return low;
}

// 改进算法:仅当每段长度大于k时,进行一次快速排序
void qsort_improve(int r[], int low, int high, int k){
	if (high - low > k)                      //长度大于k时递归, k为指定的数
	{
		int pivot = partitions(r, low, high); // 调用的Partition算法保持不变
		qsort_improve(r, low, pivot - 1, k);
		qsort_improve(r, pivot + 1, high, k);
	}
}

//递归进行地快速排序
void quickSort(int r[], int n, int k)
{
	//先调用改进算法Qsort使之基本有序
	qsort_improve(r, 0, n, k);

	//再用插入排序对基本有序序列排序
	int i, j,temp;
	for (i = 1; i <= n; i++)//因为当i=0时,无意义,故从下标1开始
	{
		temp = r[i];
		j = i - 1;
		while (temp<r[j])//升序
		{
			r[j + 1] = r[j];
			j--;
			r[j + 1] = temp;
		}
	}
}

void main()
{
	int a[10] = { 3, 1, 5, 7, 2, 4, 9, 6, 10, 8 };
	printf("初始值:");
	print(a, 10);
	quickSort(a, 9, 4);
	printf("排序后:");
	print(a, 10);

	getchar();
}

排序结果:

 

算法复杂度

最坏情况下的快排时间复杂度:

最坏情况发生在划分过程产生的俩个区域分别包含n-1个元素和一个0元素的时候,
即假设算法每一次递归调用过程中都出现了,这种划分不对称。那么划分的代价为O(n),
因为对一个大小为0的数组递归调用后,返回T(0)=O(1)。
估算法的运行时间可以递归的表示为:

T(n)=T(n-1)+T(0)+O(n)=T(n-1)+O(n).

可以证明为T(n)=O(n^2)。

因此,如果在算法的每一层递归上,划分都是最大程度不对称的,那么算法的运行时间就是O(n^2)。

最快情况下快排时间复杂度:

最快情况下,即PARTITION可能做的最平衡的划分中,得到的每个子问题都不能大于n/2.

因为其中一个子问题的大小为|n/2|。另一个子问题的大小为|-n/2-|-1.

在这种情况下,快速排序的速度要快得多:

T(n)<=2T(n/2)+O(n).可以证得,T(n)=O(nlgn)。

© 著作权归作者所有

Master_Li
粉丝 1
博文 74
码字总数 57794
作品 0
南京
程序员
私信 提问
快速排序实现及其pivot的选取

coursera上斯坦福的算法专项在讲到快速排序时,称其为最优雅的算法之一。快速排序确实是一种比较有效的排序算法,很多类库中也都采用了这种排序算法,其最坏时间复杂度为$O(n^2)$,平均时间复...

xinyuexy
2018/10/05
0
0
快速排序实现及pivot的选取

coursera上斯坦福的算法专项在讲到快速排序时,称其为最优雅的算法之一。快速排序确实是一种比较有效的排序算法,很多类库中也都采用了这种排序算法,其最坏时间复杂度为,平均时间复杂度为,...

xinyuexy
2018/09/14
0
0
JDK提供的排序算法是怎么实现的?

前几天整理的一套面试题,其中有一个问题就是Java的JDK中我们见到的Collections.sort()和Arrays.sort()这两个排序算法的实现方式是什么,很多小伙伴心里边默认的应该是快排,但是不全对或者理...

HOT_POT
2018/07/29
0
0
接触并理解 快速排序【基础+优化+三向切分】

要点 算法思想与实现,优化思路,性能分析,三向切分,空间,优势 前言 快速排序之所以被称作“快速”,是因为快速排序是我们接触到的最快的通用排序算法,至于原因我们会在后面予以解释。鉴...

LWADE
2017/12/07
0
0
java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯
2018/06/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

4.01、Linux异常

1、无法连接虚拟设备ide1:0,因为主机上没有响应的设备 解决方法:找到“虚拟机” —— 打开“虚拟机设置” —— 单击“CD/DVD(IDE)”,右侧选中“使用ISO映像文件”,然后选中自己的镜像,重启...

静以修身2025
20分钟前
0
0
不允许有匹配 "[xX][mM][lL]" 的处理指令目标

Bug解决方案:org.xml.sax.SAXParseException; lineNumber: 1; columnNumber: 8; 不允许有匹配 "[xX][mM][lL]" 的处理指令目标 Caused by: org.xml.sax.SAXParseException; lineNumber: 1; c......

我叫小糖主
24分钟前
0
0
Mysql InnoDB 行锁和表锁介绍

mysql 的 InnoDB引擎支持行锁,与Oracle不同,mysql的行锁是通过索引加载的,即是行锁是加在索引响应的行上的,要是对应的SQL语句没有走索引,则会全表扫描,行锁则无法实现,取而代之的是表...

嘴角轻扬30
24分钟前
1
0
springboot+jpa 错误信息org.springframework.beans.factory.BeanCreationException

报错信息 org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'entityManagerFactory' defined in class path resource [org/springframework/boot/a......

冥焱
42分钟前
1
0
威胁快报|新兴挖矿团伙借助shodan作恶,非web应用安全再鸣警钟

近日,阿里云安全发现了一个使用未授权访问漏洞部署恶意Docker镜像进行挖矿的僵尸网络团伙。我们给这一团伙取名为Xulu,因为该团伙使用这个字符串作为挖矿时的用户名。 Xulu并不是第一个攻击...

迷你芊宝宝
49分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部