快速排序c++,Python,Cpython

发表时间:2021-05-11

在这里插入图片描述
快速排序由C. A. R. Hoare在1962年提出。它的 基本思想是 :通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

1.性质

快排的时间复杂度分析


时间复杂度:
    最优情况:O(nlogn)
	最坏情况:O(n2)
空间复杂度:O(logn)

该排序算法不稳定


排序算法 稳定性 的概念

假定在待排序的记录序列中,存在多个具有相同的元素的
(用下标表征其相对位置),若经过排序,这些元素的相对次序保持不变,
即在原序列中,r[i]=r[j],且r[i]在r[j]之前,

而在排序后的序列中,r[i]仍在r[j]之前,
则称这种排序算法是稳定的;否则称为不稳定的。

总结一下就是:
对于两个大小相同的元素,每次排序后其相对位置如果不改变(下标i不会跑到j后面),那么就叫稳定。

算法稳定性为什么这么重要呢?

1)在实际的应用中,我们交换的不一定只是一个整数,而可能是一个很大的对象,交换元素存在一定的开销;
2)不稳定排序是无法完成基数排序的
参考来源:排序算法的稳定性

2.C++程序

#include<iostream>
using namespace std;

void quicksort(int *arr, int l, int r)
{
	if (l < r)
	{
		int tmp = arr[l];
		int i = l, j = r;
		while (i < j)
		{
			// 每一轮交换后的结果就是,左边都比tmp小,右边都比tmp大
			while (i<j && arr[j]>tmp)
				j--;
			arr[i] = arr[j];//遇到一个arr[j]比tmp小,放前面去
			while (i < j && arr[i] < tmp)
				i++;
			arr[j] = arr[i];//遇到一个arr[i]比tmp大,放后面去
		}
		arr[i] = tmp; // 一轮交换结束,i=j,跳出循环,此时tmp应该在的位置
		quicksort(arr, l, i - 1);
		quicksort(arr, i + 1, r);
	}
}
int main()
{
	
	int arr[] = { 5,1,3,6,8,9 };
	int len = sizeof(arr) / sizeof(arr[0]);
	quicksort(arr, 0, len-1);//这里一定是len-1,下标不能越界
	cout << "排序结果:" << endl;
	for (auto c : arr)
		cout << c << " ";
	system("pause");
	return 0;
}

3.python程序

def quicksort(arr,l,r):
    # 返回条件
    if r<= l:
        return 
    i = l
    j = r
    tmp = arr[l]
    while i<j :
        while i<j and arr[j]>tmp:
            j -= 1
        arr[i] = arr[j]
        while i<j and arr[i]<tmp:
            i += 1
        arr[j] = arr[i]
    arr[i] = tmp
    quicksort(arr,l, i-1)
    quicksort(arr, i+1, r)


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    quicksort(alist, 0, len(alist) - 1)
    print(alist)


文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号-4
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free