-
常见的几种排序方法(冒泡排序、选择排序、插入排序、快速排序等)
2019-10-17 10:45:51插入排序,堆排序,选择排序,归并排序,快速排序,冒泡排序都是比较排序,它们通过对数组中的元素进行比较来实现排序,其他排序算法则是利用非比较的其他方法来获得有关输入数组的排序信息。 冒泡排序 冒泡排序...排序算法有很多,包括插入排序,冒泡排序,堆排序,归并排序,选择排序,计数排序,基数排序,桶排序,快速排序等。
十种常见排序算法可以分为两大类:
非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。
线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。
算法优劣评价术语
稳定性:
稳定:如果 a 原本在 b 前面,而 a = b,排序之后 a 仍然在 b 的前面;
不稳定:如果 a 原本在 b 的前面,而 a = b,排序之后 a 可能会出现在 b 的后面;排序方式:
内排序:所有排序操作都在内存中完成,占用常数内存,不占用额外内存。
外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行,占用额外内存。复杂度:
时间复杂度: 一个算法执行所耗费的时间。
空间复杂度: 运行完一个程序所需内存的大小。
冒泡排序
冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。
依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。
在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。
由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。
选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素, 然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 选择排序的思想其实和冒泡排序有点类似,都是在一次排序后把最小的元素放到最前面。但是过程不同, 冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。
插入排序
有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法–插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。
它的 工作原理是通过构建有序序列,对于未排序数据, 在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序 (即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位, 为最新元素提供插入空间。
1.从第一个元素开始,该元素可以认为已经被排序
2.取出下一个元素,在已经排序的元素序列中从后向前扫描
3.如果该元素(已排序)大于新元素,将该元素移到下一位置
4.将新元素插入到该位置后快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort), 一种排序算法, 最早由东尼·霍尔提出。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较, 但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)演算法更快, 因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
步骤为:
从数列中挑出一个元素,称为"基准"(pivot),
重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割(partition)操作。
递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个演算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。换一种表述:
快速排序的基本思想是,通过一轮的排序将序列分割成独立的两部分,其中一部分序列的关键字(这里主要用值来表示)均比另一部分关键字小。继续对长度较短的序列进行同样的分割,最后到达整体有序。在排序过程中,由于已经分开的两部分的元素不需要进行比较,故减少了比较次数,降低了排序时间。
详细描述:首先在要排序的序列 a 中选取一个中轴值,而后将序列分成两个部分,其中左边的部分 b 中的元素均小于或者等于 中轴值,右边的部分 c 的元素 均大于或者等于中轴值,而后通过递归调用快速排序的过程分别对两个部分进行排序,最后将两部分产生的结果合并即可得到最后的排序序列。
“基准值”的选择有很多种方法。最简单的是使用第一个记录的关键字值。但是如果输入的数组是正序或者逆序的,就会将所有的记录分到“基准值”的一边。较好的方法是随机选取“基准值”,这样可以减少原始输入对排序造成的影响。但是随机选取“基准值”的开销大。
参考:
https://blog.csdn.net/weixin_40205234/article/details/86699088
课本(教材)原话(清华大学出版社《数据结构》严蔚敏、吴伟民):
以上排序均属于内部排序,运行在RAM中。
-
JavaScript实现in-place思想的快速排序方法
2021-01-21 12:21:26快速排序的思想 数组中指定一个元素作为标尺,比它大的放到该元素后面,比它小的放到该元素前面,如此重复直至全部正序排列。 快速排序分三步: 选基准:在数据结构中选择一个元素作为基准(pivot) 划分区:参照基准... -
交换排序(冒泡排序,优化冒泡排序,快速排序,以及快速排序优化的三种方法详解)
2019-03-04 21:29:30交换排序:利用交换元素的位置进行排序的方法称为交换排序。常用的交换排序有冒泡排序和快速排序。 冒泡排序算法: 基本思想:n个元素,序列进行N-1次循环,依次比较相邻两个元素的大小,如果array[i]>...交换排序:利用交换元素的位置进行排序的方法称为交换排序。常用的交换排序有冒泡排序和快速排序。
冒泡排序算法:
基本思想:n个元素,序列进行N-1次循环,依次比较相邻两个元素的大小,如果array[i]>array[i+1],则交换两个元素,反之则不交换。这样每次循环都能比较出数值最大的那个元素。
最好最坏情况:
最好情况是正序,时间复杂度是O(N),比较次数为n-1次
最坏情况是逆序,时间复杂度是O(N2),比较次数为n(n-1)/2
步骤:
初始序列:49 38 65 97 76 13 27 49*
-
38 49 65 76 13 27 49* 97
-
38 49 65 13 27 49* 76 97
-
38 49 13 27 49* 65 76 97
-
38 13 27 49 49* 65 76 97
-
13 27 38 49 49* 65 76 97
-
13 27 38 49 49* 65 76 97
-
13 27 38 49 49* 65 76 97
-
13 27 38 49 49* 65 76 97
根据过程可以看出冒泡排序是一个稳定排序算法。
算法代码:
//冒泡排序(稳定算法) void MaoPaoSort(int *array,int len) { int i, j; int temp; for (i = 0; i < len; ++i) { for (j = 1; j < len - i; j++) { if (array[j] <array[j-1]) { temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } }
可以将冒泡排序进行优化:
如果某一趟已经将序列排好,程序再继续运行就是多余的,我们可以将其终止。
算法代码:
void MaoPaoSort(int *array,int len) { int i, j; int temp; int flag = 0; for (i = 0; i < len&&flag==0; ++i) { flag = 1; for (j = 1; j < len - i; j++) { if (array[j] <array[j-1]) { temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; flag = 0; } } } }
快速排序是冒泡排序的一种改进。
基本思想:
在待排序的序列中选取一个基准值,通常为第一个数字
然后经过一趟排序将这个序列分割成独立的两部分,
其中,比基准值小的数字放在左边,比基准值大的数字放在右边,
则可对这两部分记录继续递归进行排序,以达到整个序列有序。
步骤过程(动图):
算法代码:
//从两端交替扫描 int Partition(int *array, int low, int high) { //选取一个基准值 int pivokey = array[low]; while (low < high)//当low==high时循环结束,按照基准值排序两边完成 { //扫描右边,直至遇到一个小于基准值的数停止 while (low<high&&array[high]>=pivokey) --high; //将这个小于基准值的数取出放入左边 array[low] = array[high]; //扫描左边,直至遇到一个大于基准值的数停止扫描 while (low < high&&array[low]<=pivokey) ++low; //将这个大于基准值的数放入右边 array[high] = array[low]; } array[low] = pivokey;//将基准值填入 return low;//返回基准值所在的位置 } //快速排序(不稳定算法) void QSort(int *array,int low,int high) { if (low < high)//长度大于1 { //找到最后填入基准值位置 int pivotic = Partition(array,low,high); //再对左边序列进行排序 QSort(array,low,pivotic-1); //对序列右边进行排序 QSort(array,pivotic+1,high); } return; }
快速排序最佳情况下时间复杂度是 O(nlogn)。但是最坏情况下可能达到O(n^2)。说明快速排序达到最坏情况的原因。并提出改善方案并实现之。
快速排序算法的几种改进:
1.随机化算法
基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望复杂度。
随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降到O(n^2)。
算法描述:
void swap(int *array, int index, int n) { int temp; temp = array[index]; array[index] = array[n]; array[n] = temp; } int Partition1(int *array,int low,int high) { if (array == nullptr || low <0) throw new std::exception("Invalid parameters\n"); //选取一个随机值 int index = (rand() % (high - low)) + low; //将随机数与第一位交换,接着就是经典的partition swap(array, index, low); //保存这个随机数 int privokey = array[low]; while (low < high) { //找到小于基准值的数 while (low<high&&array[high]>=privokey) high--; if (low < high) { array[low] = array[high]; } while (low < high&&array[low] <=privokey) low++; if (low < high) { array[high] = array[low]; } } array[low] = privokey; return low; }
2.三平均分区法
与一般的快速排序方法不同,它并不是选择待排数组的第一个待排数组第一个数作为中轴。而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为轴。
算法代码:
//求三个数中位数,并将其放在初始位置。 void GetThreeValue(int *array, int low, int high) { int mid = (low + (high - low)) >> 1; //先把最大的数放入到high位置,然后比较mid和low,如果mid比low大,则说明mid是中间值,放入low位置 if (array[mid] > array[high]) { swap(array,mid,high); } if (array[low] > array[high]) { swap(array,low,high); } if (array[mid] > array[low]) { swap(array,mid,low); } } //三平均分区法,可以使最坏情况的几率大大减小(减小退化问题) int Partition2(int *array, int low, int high) { if (array == nullptr || low < 0||low>high) throw new std::exception("Invalid Parameters\n"); GetThreeValue(array, low, high); int privokey = array[low]; while (low < high) { while (low < high&&array[high] >= privokey) high--; if (low<high) { array[low] = array[high]; } while (low < high&&array[low] <= privokey) { low++; } if (low < high) { array[high] =array[low]; } } array[low] = privokey; return low; }
3.每次选取数据集中的中位数做基准值。
其他可以改进的地方(网络搜集) :
1、 快速排序在处理小规模数据时的表现不好.
这个时候可以改用插入排序。
当数据规模小于一定程度时,改用插入排序。具体小到何种规模时,采用插入排序,这个理
论上还不解,一些文章中说是 5 到 25 之间。SGI STL 中的快速排序采用的值是 10.
2、对于一个每个元素都完全相同的一个序列来讲,快速排序也会退化到 O(n^2)。
要将这种情况避免到,可以这样做:
在分区的时候,将序列分为 3 堆,一堆小于中轴元素,一堆等于中轴元素,一堆大于中轴元
素,下次递归调用快速排序的时候,只需对小于和大于中轴元素的两堆数据进行排序,中间
等于中轴元素的一堆已经放好。
参考博客:https://blog.csdn.net/lingfengtengfei/article/details/12376889
-
-
优化快速排序的几种方法
2017-10-25 12:00:14经过一趟排序将待排序序列分割为独立的两部分,其中一部分的所有排序关键字均小于另一部分的所有排序关键字,再按上述方法对序列的两部分分别进行快速排序,整个排序过程可以递归执行,最终达到整个序列有序的目的。...快速排序
1.基本思想
快速排序采用分治思想。经过一趟排序将待排序序列分割为独立的两部分,其中一部分的所有排序关键字均小于另一部分的所有排序关键字,再按上述方法对序列的两部分分别进行快速排序,整个排序过程可以递归执行,最终达到整个序列有序的目的。
2.算法概述
分解:在待排序数列按照某种特定选取一个元素作为主元。利用主元对序列进行重排,使得序列分成独立的两个部分,其中一部分的所有排序关键字均小于另一部分的所有排序关键字,即序列所有排序关键字小于主元的排序关键字的元素置于主元的左侧,其他元素置于右侧。
。
解决:通过递归对主元左侧的序列已经右侧的序列进行快速排序来去求解子问题。
合并:因为快速排序是原址操作,所以不需要执行合并操作,同时也节省了部分空间。3.算法实现(Python)
# coding = utf-8 """ 快速排序的一些优化方式 """ import random import time def quick_sort(lst, first=0, last=0): # 快速排序 if first >= last: return lst low = first high = last pivot = lst[first] # 选取第一个为主元 while first < last: while first < last and lst[last] >= pivot: last -= 1 lst[first] = lst[last] while first < last and lst[first] <= pivot: first += 1 lst[last] = lst[first] lst[last] = pivot quick_sort(lst, low, first - 1) quick_sort(lst, first + 1, high)
4. 算法分析
运行时间
快速排序的最坏时间复杂度是Θ(n2),平均情况下的时间复杂度为Θ(nlgn)。快速排序的渐近时间复杂度介于最坏情况和平均情况。
这里分别采用确定的快速排序(即选取序列的第一个元素或最后一个序列为主元)分别针对输入规模>500万的序列进行排序,获得确定的快速排序的运行时间。输入规模500万的序列排序运行时间
算法 随机序列 重复序列 升序序列 降序序列 确定的快速排序 36084ms 递归深度过大,堆栈溢出 同左 同左 python内置sort方法 5372ms 93ms 184ms 99ms 测试数据分析
在针对输入序列的数据是随机的时,我们设计的快速排序的效率是可以接受的。针对输入序列是有序的时候,虽然因为递归深度过大,导致堆栈溢出(Python的解释器没有针对做优化),无法成功执行完程序,但是我们也可以预料到,每次排序划分长度都是1,也就是说我们需要将序列划分500万次,才能使序列重新有序,其时间复杂度和空间复杂度可想而知。此时的情况为最坏的情况即时间复杂度为Θ(n2),即沦为普通的冒泡排序。在实际情况中,输入序列很有可能是有序的或者是部分有序的,这时我们可以通过在算法中引入随机性,使得算法对所有的输入都能获得较好的期望性能,同时将随机化版本的快速排序被更多的人运用在大数据输入情况下的排序算法。优化方式1:引入随机性
随机选取主元元素
# coding = utf-8 """ 优化方法1:引入随机性 """ import random import time def quick_sort(lst, first=0, last=0): # 快速排序 if first >= last: return lst low = first high = last pivot_index = random.randint(first, last) # 随机选取主元位置 lst[first], lst[pivot_index] = lst[pivot_index], lst[first] # 将主元置于首位 pivot = lst[first] while first < last: while first < last and lst[last] >= pivot: last -= 1 lst[first] = lst[last] while first < last and lst[first] <= pivot: first += 1 lst[last] = lst[first] lst[last] = pivot quick_sort(lst, low, first - 1) quick_sort(lst, first + 1, high)
输入规模500万的序列排序的运行时间
算法 随机序列 重复序列 升序序列 降序序列 随机化快速排序 45830ms 递归深度过大,堆栈溢出 29147ms 29363ms python内置sort方法 6027ms 139ms 113ms 122ms 测试数据分析
通过引入随机性,我们较好的解决了序列有序的时候出现的问题,但是仍然存在一个问题那就是如果序列为重复的数据或者数据大量重复的情况,只引入随机化并不能很好的解决问题。这时候我们可以通过将排序关键字与主元相等的元素聚集在一起,下次不再对这些元素进行分割,这不仅可以解决目前的设计的算法在重复序列上存在的问题,也可以一定程度上优化对其他序列排序的效率。优化方式2:聚集
# coding = utf-8 """ 优化方法1:引入随机性 优化方法2:聚集 """ import random import time def quick_sort(lst, first=0, last=0): # 快速排序 if first >= last: return lst low = first high = last left_lst_len = 0 # 分割后第一个序列和第二个序列与主元相等元素的长度 right_lst_len = 0 # 选取随机的主元,并将主元元素与第一个元素置换 pivot_index = random.randint(first, last) lst[first], lst[pivot_index] = lst[pivot_index], lst[first] pivot = lst[first] while first < last: while first < last and lst[last] >= pivot: if lst[last] == pivot: right_lst_len += 1 last -= 1 lst[first] = lst[last] while first < last and lst[first] <= pivot: if lst[first] == pivot: left_lst_len += 1 first += 1 lst[last] = lst[first] lst[last] = pivot lst1_last = first - 1 # 保存分割后第一个序列的最后位置和第二个序列的最开始的位置 lst2_first = first + 1 flag = low while lst1_last - low > 0 and flag < lst1_last and left_lst_len > 0: # 将第一个序列中与主元相等的元素置于主元左侧 if pivot == lst[flag]: while lst[lst1_last] == pivot and left_lst_len > 0 and lst1_last - low > 0: left_lst_len -= 1 lst1_last -= 1 if lst1_last > 0 and left_lst_len > 0: lst[flag], lst[lst1_last] = lst[lst1_last], lst[flag] left_lst_len -= 1 lst1_last -= 1 else: break flag += 1 flag = high while high - lst2_first > 0 and flag > lst2_first and right_lst_len > 0: # 将第二个序列中与主元相等的元素置于主元右侧 if pivot == lst[flag]: while lst[lst2_first] == pivot and right_lst_len > 0 and high - lst2_first > 0: right_lst_len -= 1 lst2_first += 1 if lst2_first < high and right_lst_len > 0: lst[flag], lst[lst2_first] = lst[lst2_first], lst[flag] right_lst_len -= 1 lst2_first += 1 else: break flag -= 1 quick_sort(lst, low, lst1_last) quick_sort(lst, lst2_first, high)
输入规模500万的序列排序的运行时间
算法 随机序列 重复序列 升序序列 降序序列 随机化快速排序+聚集 63856ms 2272ms 38797ms 42183ms python内置sort方法 7682ms 88ms 95ms 103ms 测试数据分析
通过将排序关键字与主元相等的元素聚集在一起,下次不再对这些元素进行分割,这不仅可以解决目前的设计的算法在重复序列上存在的问题,也可以一定程度上优化对其他序列排序的效率,如果序列的重复度(即重复出现的数据所占比例)越大,聚集所提高的效率越大。优化方式3:三位数取中
取序列中lst[first]、lst[mid]、lst[last]中的中位数作为主元
# coding = utf-8 """ 优化方法2:聚集 优化方法3:三位数取中 """ import random import time def quick_sort(lst, first=0, last=0): # 快速排序 if first >= last: return lst low = first high = last left_lst_len = 0 # 分割后第一个序列和第二个序列与主元相等元素的长度 right_lst_len = 0 select_pivot_median(lst, first, last) # 选择主元并将置于首位 pivot = lst[first] while first < last: while first < last and lst[last] >= pivot: if lst[last] == pivot: right_lst_len += 1 last -= 1 lst[first] = lst[last] while first < last and lst[first] <= pivot: if lst[first] == pivot: left_lst_len += 1 first += 1 lst[last] = lst[first] lst[last] = pivot lst1_last = first - 1 # 保存分割后第一个序列的最后位置和第二个序列的最开始的位置 lst2_first = first + 1 flag = low while lst1_last - low > 0 and flag < lst1_last and left_lst_len > 0: # 将第一个序列中与主元相等的元素置于主元左侧 if pivot == lst[flag]: while lst[lst1_last] == pivot and left_lst_len > 0 and lst1_last - low > 0: left_lst_len -= 1 lst1_last -= 1 if lst1_last > 0 and left_lst_len > 0: lst[flag], lst[lst1_last] = lst[lst1_last], lst[flag] left_lst_len -= 1 lst1_last -= 1 else: break flag += 1 flag = high while high - lst2_first > 0 and flag > lst2_first and right_lst_len > 0: # 将第二个序列中与主元相等的元素置于主元右侧 if pivot == lst[flag]: while lst[lst2_first] == pivot and right_lst_len > 0 and high - lst2_first > 0: right_lst_len -= 1 lst2_first += 1 if lst2_first < high and right_lst_len > 0: lst[flag], lst[lst2_first] = lst[lst2_first], lst[flag] right_lst_len -= 1 lst2_first += 1 else: break flag -= 1 quick_sort(lst, low, lst1_last) quick_sort(lst, lst2_first, high) def select_pivot_median(lst, first, last): # 将选取的主元即lst[first],lst[mid],lst[last]的中位数置于first坐标位置 mid = first + ((last - first) >> 1) # 计算序列中间元素的下标 if lst[mid] > lst[last]: lst[mid], lst[last] = lst[last], lst[mid] if lst[first] > lst[last]: lst[first], lst[last] = lst[last], lst[first] if lst[mid] > lst[first]: lst[mid], lst[first] = lst[first], lst[mid]
输入规模500万的序列排序的运行时间
算法 随机序列 重复序列 升序序列 降序序列 三数取中的快速排序+聚集 53375ms 2550ms 30123ms 35552ms python内置sort方法 5767ms 88ms 126ms 103ms 测试数据分析
通过引入随机性提高序列分割的效率,但是其最坏情况下的时间复杂度仍然是Θ(n2)。最佳情况下的划分是可以将待排序的序列划分为等长的序列,也就是说我们选取的主元是整个序列的中位数,但是如果要求整个序列的中位数那必定会花费更多的时间,有点得不偿失的感觉。我们可以选取折中的办法,选择最左端、中心位置、最右端的元素中的中位数作为组元,能一定程度上快速排序的比较次数。优化方式4:引入插入排序
插入排序在待排序序列长度一定时效率高于插入排序,我们可以在快速排序分割的子序列长度达到一定时采用插入排序进行排序
# coding = utf-8 """ 优化方法2:聚集 优化方法3:三位取中 优化方法4:插入排序 """ import random import time def quick_sort(lst, first=0, last=0): if last - first + 1 > 10: insert_sort(lst, first, last) else: # 快速排序 if first >= last: return lst low = first high = last left_lst_len = 0 # 分割后第一个序列和第二个序列与主元相等元素的长度 right_lst_len = 0 select_pivot_median(lst, first, last) # 选择主元并将置于首位 pivot = lst[first] while first < last: while first < last and lst[last] >= pivot: if lst[last] == pivot: right_lst_len += 1 last -= 1 lst[first] = lst[last] while first < last and lst[first] <= pivot: if lst[first] == pivot: left_lst_len += 1 first += 1 lst[last] = lst[first] lst[last] = pivot lst1_last = first - 1 # 保存分割后第一个序列的最后位置和第二个序列的最开始的位置 lst2_first = first + 1 flag = low while lst1_last - low > 0 and flag < lst1_last and left_lst_len > 0: # 将第一个序列中与主元相等的元素置于主元左侧 if pivot == lst[flag]: while lst[lst1_last] == pivot and left_lst_len > 0 and lst1_last - low > 0: left_lst_len -= 1 lst1_last -= 1 if lst1_last > 0 and left_lst_len > 0: lst[flag], lst[lst1_last] = lst[lst1_last], lst[flag] left_lst_len -= 1 lst1_last -= 1 else: break flag += 1 flag = high while high - lst2_first > 0 and flag > lst2_first and right_lst_len > 0: # 将第二个序列中与主元相等的元素置于主元右侧 if pivot == lst[flag]: while lst[lst2_first] == pivot and right_lst_len > 0 and high - lst2_first > 0: right_lst_len -= 1 lst2_first += 1 if lst2_first < high and right_lst_len > 0: lst[flag], lst[lst2_first] = lst[lst2_first], lst[flag] right_lst_len -= 1 lst2_first += 1 else: break flag -= 1 quick_sort(lst, low, lst1_last) quick_sort(lst, lst2_first, high) def select_pivot_median(lst, first, last): # 将选取的主元即lst[first],lst[mid],lst[last]的中位数置于first坐标位置 mid = first + ((last - first) >> 1) # 计算序列中间元素的下标 if lst[mid] > lst[last]: lst[mid], lst[last] = lst[last], lst[mid] if lst[first] > lst[last]: lst[first], lst[last] = lst[last], lst[first] if lst[mid] > lst[first]: lst[mid], lst[first] = lst[first], lst[mid] def insert_sort(lst, first, last): # 插入排序 for index in range(first + 1, last + 1): key = lst[index] j = index - 1 while j >= first: if lst[j] > key: lst[j + 1] = lst[j] lst[j] = key j -= 1
输入规模500万的序列排序的运行时间
算法 随机序列 重复序列 升序序列 降序序列 三数取中的快速排序+聚集+插入排序 40934ms 2549ms 21389ms 34769ms python内置sort方法 5690ms 88ms 119ms 124ms 测试数据分析
针对长度较小或者部分有序数组时,插入排序的效率优于快速排序,引入插入排序将会使算法整体效率略有提高,而且这个方法适用于大部分序列。其他优化方式
优化递归操作
我们可以使用尾递归的方式对快速排序的递归操作进行处理,来减少递归层次,避免堆栈溢出的发生,可以解决确定的快速排序无法处理已排序序列的问题
【待完成】。
使用并行算法或者多线程算法处理子序列
【待完成】总结
快速排序的优化细节没有处理好,导致算法的整体效率没有很大的提升,以后有时间对算法细节进行处理,可以达到更佳的效果。另外输入数据都是随机生成的,导致有的优化甚至比没优化之前排序所花费的时间更多,这除了细节问题,还有数据特征不符合现实生活。现实生活中的数据经常是部分有序的序列,所以如果采用优化后的算法,实际运行情况会比当前测试的情况更佳。
参考资料
http://blog.csdn.net/hacker00011000/article/details/52176100 -
寻找数组中最小的k个数 "利用快速排序的思想
2013-10-18 00:33:46主要思想是:类似快速排序的划分方法, N个数存储在数组S中, 再从数组中随机选取一个数X(随机选取枢纽元, 可做到线性期望时间O(N)的复杂度), 把数组划分为Sa和Sb俩部分, Sa, 如果要查找的k个元素小于Sa的元素个数, 则...主要思想是:类似快速排序的划分方法, N个数存储在数组S中, 再从数组中随机选取一个数X(随机选取枢纽元, 可做到线性期望时间O(N)的复杂度), 把数组划分为Sa和Sb俩部分, Sa<=X<=Sb, 如果要查找的k个元素小于Sa的元素个数, 则返回Sa中较小的k个元素, 否则返回Sa中所有元素+Sb中小的k-|Sa|个元素. 像上述过程一样, 这个运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素, 在最坏情况下亦能做到O(N)的复杂度. 不过值得一提的是, 这个快速选择SELECT算法是选取数组中"中位数的中位数"作为枢纽元, 而非随机选取枢纽元.
1. If |S| = 1, then k = 1 and return the elements in S as the answer. If a cutoff for small files is being used and |S| <=CUTOFF, then sort S and return the kth smallest element.
2. Pick a pivot element, v (- S.(选取一个枢纽元v属于S)
3. Partition S - {v} into S1 and S2, as was done with quicksort.
(将集合S-{v}分割成S1和S2,就像我们在快速排序中所作的那样)4. If k <= |S1|, then the kth smallest element must be in S1. In this case, return quickselect (S1, k). If k = 1 + |S1|, then the pivot is the kth smallest element and we can return it as the answer. Otherwise, the kth smallest element lies in S2, and it is the (k - |S1| - 1)st smallest element in S2. We make a recursive call and return quickselect (S2, k - |S1| - 1).
(如果k<=|S1|,那么第k个最小元素必然在S1中。在这种情况下,返回quickselect(S1,k)。如果k=1+|S1|,那么枢纽元素就是第k个最小元素,即找到,直接返回它。否则,这第k个最小元素就在S2中,即S2中的第(k-|S1|-1)个最小元素,我们递归调用并返回quickselect(S2,k-|S1|-1))。/*利用快速排序的思想实现寻找数组中最小的k个元素*/ /* 1. If |S| = 1, then k = 1 and return the elements in S as the answer. If a cutoff for small files is being used and |S| <=CUTOFF, then sort S and return the kth smallest element. 2. Pick a pivot element, v (- S.(选取一个枢纽元v属于S) 3. Partition S - {v} into S1 and S2, as was done with quicksort.(将集合S-{v}分割成S1和S2,就像我们在快速排序中所作的那样) 4. If k <= |S1|, then the kth smallest element must be in S1. In this case, return quickselect (S1, k). If k = 1 + |S1|, then the pivot is the kth smallest element and we can return it as the answer. Otherwise, the kth smallest element lies in S2, and it is the (k - |S1| - 1)st smallest element in S2. We make a recursive call and return quickselect (S2, k - |S1| - 1). */ //q_select places the kth smallest element in a[k] void q_select(input_type a[], int k, int left, int right) { int i,j; input_type pivot; if( left+CUTOFF <= right) { pivot = median3( a, left, right); //取三数中值作为枢纽元,可以消除最坏情况而保证此算法是O(N)的.不过,这还只局限在理论意义上. i = left; j = right-1; for(;;) { while(a[++i]<pivot); while(a[--j]>pivot); if(i<j) swap(&a[i],&a[j]); else break; } swap(&a[i],&a[right-1]); //restore pivot if(k<i) q_select(a,k,left,i-1); else if(k>i) q_select(a,k-i,i+1,right); } else insert_sort(a,left,right); }
1. 与快速排序相比, 快速选择只做了一次递归调用而不是两次. 快速选择的最坏情况和快速排序的相同, 也是O(N^2), 最坏情况发生在枢纽元的选取不当, 以致S1,或S2中有一个序列为空;
2. 这就好比快速排序的运行时间与划分时否对称有关, 划分的好或对称, 那么快速排序可达最佳的运行时间O(n*logn), 划分的不好或不对称, 则会有最坏的运行时间为O(N^2). 而枢纽元的选择完全决定快速排序的partition过程是否划分对称.
3. 快速选择也是一样, 如果枢纽元的选取不当, 则依然会有最坏的运行时间为O(N^2)的情况发生. 那么, 怎么避免这个最坏情况的发生, 或者说就算是最坏情况下, 亦能保证快速选择的运行时间为O(N)? 关键, 还是看你的枢纽元怎么选取.
4. 像上述程序使用三数中值作为枢纽元的方法可以使得最坏情况发生的概率几乎可以忽略不计. 然而, 通过一种更好的方法, 如“五分化中项的中项”, 或"中位数的中位数"等方法选取枢纽元, 我们将能彻底保证在最坏情况下依然是线性O(N)的复杂度.
-
partition方法,及利用其进行快速排序,输出最小的k个值等操作
2019-05-11 16:12:30partition算法就是把数组分割成几部分,对于快速排序中的分割算法就是把数组分割成大于某个数的一部分和小于一个数的一部分 partition方法从目的上看是达到以下三点: 选中数组中某一个元素,即为suanz(可以是... -
快速排序方法及代码
2020-08-12 14:37:10这是一个利用递归排序的算法。 给我一组序列(未必是数组,也可以是链表),首先要知道其长度。 定义一个函数,输入参数要包括待排序的序列指针,子序列起始元素索引low,终止元素索引high。 1.将起始元素存于临时... -
三种排序方法的实现以及性能比较(快速排序,插入排序,选择排序)
2020-11-07 17:11:08若图片无法显示请前往上方我博客的链接! 最近开始学算法了,在学校搞定了三种排序,刚刚在...那么就先依次上代码吧,在此之前我先利用Java的继承体系做了一个排序模板(里面记录了所有排序都必定会要用到的方法) Sort.ja -
快速排序
2019-04-17 18:59:21快速排序算法利用的是一趟快速排序,基本内容是选择一个数作为准基数,然后利用这个准基数将遗传数据分为两个部分,第一部分比这个准基数小,都放在准基数的左边,第二部分都比这个准基数大,放在准基数的右边. ... -
Javascript利用递归实现数组的快速排序
2016-06-14 11:19:00// 定义快速排序方法 function quickSort(arr){ // 设置递归的终止条件 if( arr.length <= 1){ return arr; } // 获得数组arr的中间索引和中间索引对应的值 var middleNum = Math.floor(arr.... -
快速排序的三种实现方法 (C++)
2018-05-08 18:57:57快速排序的中心思想 快速排序利用的是分治思想,将一个大数组的排序划分为多个小数组的排序,最后进行合并便是排序的结果。 首先,需要从数组中选择一个主元,通常为数组的第一个元素或最后一个元素(好操作)。接... -
利用python详讲快速排序算法
2018-11-22 13:38:20它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个... -
经典算法之快速排序的C实现方法
2015-06-06 18:25:54这里所实现的快速排序是参考《算法导论》上的伪代码,虽然之前对着伪代码敲过一遍,可是现在抛开伪代码,自己敲还是有些费劲。!!特别需要注意的是算法导论中的快排方法,和课上讲的不太一样,课上讲的主要是利用首尾... -
点击Ehlib列标题的快速排序方法
2009-05-02 10:04:00我写的这个排序函数,利用ADO的sort方法,排序很快,几万条数据也是很快。该函数支持Lookup字段排序,不支持计算字段排序,因为计算字段值在内存里高速运算。排序分为:升序、降序和默认三种,支持排序图标。 ... -
利用sort对数组快速排序
2017-09-11 09:47:00// sort内部使用快速排序,每次比较两个元素大小的时候如果没有参数,则直接判断字母表,如果有参数,则把正在比较的两个参数传入自定义方法并调用(正在比较的两个数会传给自定义方法的v1、v2),如果返回值大于0... -
利用Python实现快速算法排序
2016-06-30 00:41:24今天我们来讲下七种常用的快速排序算法中的快速排序...其基本思想就是:通过一趟排序将要排序的数据分割成独立的两个部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按次方法对这两部分数据分别进 -
算法导论 — 思考题7-3 另一种快速排序的分析方法
2019-03-23 23:55:08(另一种快速排序的分析方法)对随机化版本的快速排序算法,还有另一种性能分析方法,这一方法关注于每一次单独递归调用的期望运行时间,而不是比较次数。 a. 证明:给定一个大小为nnn的数组,任何特定元素被选为... -
MySQL利用索引优化ORDER BY排序语句的方法
2021-01-19 21:41:11创建表&创建索引 ...MySQL也能利用索引来快速地执行ORDER BY和GROUP BY语句的排序和分组操作。 通过索引优化来实现MySQL的ORDER BY语句优化: 1、ORDER BY的索引优化 如果一个SQL语句形如: SELECT -
【校招】快速排序题解
2018-03-08 15:49:10【例题|唯品会】一组记录的关键值为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录的关键值46为基准得到的一次划分结果为()。原式:46,79,56,38,40,84 1、基于原式,以46作为基准46 79 56 38...