-
2021-02-25 14:54:29
快速排序分三大步骤:
1.分:选择一个分割值并将数据按此分为左右两部分
2.治:分别在两部分用递归方式调用上述的分步骤,继续划分
3.合:对分割的部分排序直至完成#include <stdio.h> #include <stdlib.h> #include <string.h> int partion(char *s,int start,int end) { //随机选取分割值 int key = s[start]; int temp; while(1) { while(s[start] < key && (start < end) ) { //从左边开始遍历,当小于分割值,则留在左边 start++; } while(s[end] > key && (end > start)) { //从右边开始遍历,当大于分割值,则留在右边 end--; } if(start >= end) { //分割值的位置已确定,左边的都小于分隔值,右边的都大于或等于分隔值 break; } else { //找到本该在右边的start元素值,和本该在左边的end元素值,对他们进行交换 temp = s[start]; s[start] = s[end]; s[end] = temp; } if(s[end] == s[start]) { //当左右两边的元素相当,则不用交换位置,将左边的遍历的位置向右边移动开始新一轮的遍历 start++; } } //此时start=end,为分隔值所在的位置 return start; } int my_qsort(char *s,int start,int end) { if(start < end) { int k = partion(s,start,end); my_qsort(s,start,k-1); //继续排序分割值的左边 my_qsort(s,k+1,end); //继续排序分割值的右边 } } int main(int argc,char *argv[]){ char *str; int num=100; if(argv[1]!=NULL) num = atoi(argv[1]); printf("num:%d\n",num); //随机生成长度为num的字符串 str = malloc(num); for(int i = 0;i < num;i++ ) { str[i] = rand()%10 + '0'; } printf("src str:%s,len:%d.\n",str,strlen(str)); my_qsort(str,0,strlen(str)-1); printf("sort str:%s.\n",str); free(str); return 0; }
随机生成长度为100的字符串,然后对字符进行排序:
更多相关内容 -
Java基于分治法实现的快速排序算法示例
2020-08-28 12:08:50主要介绍了Java基于分治法实现的快速排序算法,结合实例形式分析了java基于分治法的快速排序相关实现技巧,代码中备有较为详细的注释说明便于理解,需要的朋友可以参考下 -
详解Java中使用泛型实现快速排序算法的方法
2020-09-02 10:12:00主要介绍了Java中使用泛型实现快速排序算法的方法,快速排序的平均时间复杂度为(nlog n),文中的方法立足于基础而并没有考虑优化处理,需要的朋友可以参考下 -
利用汇编语言实现快速排序,汇编语言排序算法
2019-05-05 10:14:01利用汇编语言实现快速排序,汇编语言排序算法。 数字逻辑与处理器大作业,通过汇编实现文件读入,快速排序,再写到文件中 汇编 快排 数逻 -
C++快速排序算法实现
2015-12-07 16:04:51简单的C++快速排序程序,对新手来说有一定的帮助,通过递归的方法完成的排序,降低时间复杂度 -
快速排序算法的简单实现
2019-03-08 14:26:04快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数中任意选出一个数,将... -
使用 Pthreads 的并行快速排序算法
2022-05-10 22:11:54为了实现快速排序算法的良好性能,对主元元素和编译器标志的选择进行了优化。为了优化性能,代码也被并行化并实现了尾递归。 由快速排序算法排序的数据是一个由 0.0 到 1.0 之间的非负双精度值组成的数组。 -
Java编程中快速排序算法的实现及相关算法优化
2020-09-02 10:13:42主要介绍了Java编程中快速排序算法的实现及相关算法优化,快速排序算法的最差时间复杂度为(n^2),最优时间复杂度为(nlog n),存在优化的空间,需要的朋友可以参考下 -
Python实现快速排序算法及去重的快速排序的简单示例
2020-09-21 15:04:39quick sort快速排序是一种再基础不过的排序算法,使用Python代码写起来相当简洁,这里我们就来看一下Python实现快速排序算法及去重的快速排序的简单示例: -
java实现快速排序算法
2020-12-18 15:34:13快速排序 1、算法思想 快速排序是由冒泡排序改进而得到的,是一种分区交换排序方法。思想如下: 一趟快速排序采用从两头向中间扫描的方法,同时交换与基准记录逆序的记录。 (1)在待排序的N个记录中任取一个元素...排序算法传送:
排序算法——java实现冒泡排序
排序算法——java实现选择排序
排序算法——java实现直接插入排序
排序算法——java实现二分法排序
排序算法——java实现希尔排序
排序算法——java实现快速排序快速排序
1、算法思想
快速排序是由冒泡排序改进而得到的,是一种分区交换排序方法。思想如下:
一趟快速排序采用从两头向中间扫描的方法,同时交换与基准记录逆序的记录。(1)在待排序的N个记录中任取一个元素(通常取第一个记录)作为基准,称为基准记录;
(2)定义两个索引 left 和 right 分别表示“首索引” 和 “尾索引”,key 表示“基准值”;
(3)首先,尾索引向前扫描,直到找到比基准值小的记录(left != righ),并替换首索引对应的值;
(4)然后,首索引向后扫描,直到找到比基准值大于的记录(left != righ),并替换尾索引对应的值;
(5)若在扫描过程中首索引等于尾索引(left = right),则一趟排序结束;将基准值(key)替换首索引对应的值;
(6)再进行下一趟排序时,待排序列被分成两个区:[0,left-1],[righ+1,end]
(7)对每一个分区重复步骤2~6,直到所有分区中的记录都有序,排序成功。图解:
2、代码实现
/** * 快速排序演示 * @author Lvan */ public class QuickSort { public static void main(String[] args) { int[] arr = {5, 1, 7, 3, 1, 6, 9, 4}; quickSort(arr, 0, arr.length - 1); for (int i : arr) { System.out.print(i + "\t"); } } /** * @param arr 待排序列 * @param leftIndex 待排序列起始位置 * @param rightIndex 待排序列结束位置 */ private static void quickSort(int[] arr, int leftIndex, int rightIndex) { if (leftIndex >= rightIndex) { return; } int left = leftIndex; int right = rightIndex; //待排序的第一个元素作为基准值 int key = arr[left]; //从左右两边交替扫描,直到left = right while (left < right) { while (right > left && arr[right] >= key) { //从右往左扫描,找到第一个比基准值小的元素 right--; } //找到这种元素将arr[right]放入arr[left]中 arr[left] = arr[right]; while (left < right && arr[left] <= key) { //从左往右扫描,找到第一个比基准值大的元素 left++; } //找到这种元素将arr[left]放入arr[right]中 arr[right] = arr[left]; } //基准值归位 arr[left] = key; //对基准值左边的元素进行递归排序 quickSort(arr, leftIndex, left - 1); //对基准值右边的元素进行递归排序。 quickSort(arr, right + 1, rightIndex); } }
3、复杂度
- 最优的情况下时间复杂度为:O( nlogn )
- 最差的情况下时间复杂度为:O( n^2 )
- 快速排序的平均时间复杂度也是:O(nlogn)
- 最优的情况下空间复杂度为:O(logn) ;每一次都平分数组的情况
- 最差的情况下空间复杂度为:O( n ) ;退化为冒泡排序的情况
-
python学习——python实现快速排序算法
2021-01-06 11:23:35python实现快速排序算法一、快速排序算法实现原理基本思想具体步骤二、图解快速排序三、py代码实现快速排序算法 一、快速排序算法实现原理 基本思想 先从数列中取出一个数作为基准数。 分区过程,将比这个数大的数...python实现快速排序算法
一、快速排序算法实现原理
基本思想
- 先从数列中取出一个数作为基准数。
- 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步,直到各区间只有一个数。
具体步骤
- 先以一个基准开始(通常为第一个数)
- 从右边开始找到第一个比基准小的数
- 从左边开始找到第一个比基准大的数
- 将比基准小的数和比基准大的数调换位置
- 继续从右往左以及从左往右调到对应的数,直到二边重合结束
- 将基准的数与重合的数调换位置,这是基准左边都是小的数,右边都是大的数
- 重复1,2,3,4对左右两边的数进行排序
二、图解快速排序
三、py代码实现快速排序算法
关键代码:
def quit_sort(arr, left, right): """快速排序算法 思想:快速排序是效率最高的排序算法之一, 1.先以一个基准开始(通常为第一个数) 2.从右边开始找到第一个比基准小的数 3.从左边开始找到第一个比基准大的数 4.将比基准小的数和比基准大的数调换位置 5.继续从右往左以及从左往右调到对应的数,直到二边重合结束 6.将基准的数与重合的数调换位置,这是基准左边都是小的数,右边都是大的数 7.重复1,2,3,4对左右两边的数进行排序 """ # 列表长度大于1 if len(arr) <= 1 or left > right: return # 定义基准 temp = arr[left] # 定义从左边开始的数(基准的下一个数) i = left # 定义从右边开始的数(要判断的末尾) j = right # 一直循环到从左边开始的碰到从右边开始的 while i < j: # 从右边开始的一直循环到第一个比基准小的数且没有碰头为止 while arr[j] >= temp and i < j: j -= 1 # 从左边开始的一直循环到第一个比基准大的数且没有碰头为止 while arr[i] <= temp and i < j: i += 1 # 当在两边找到符合条件且没有碰头的数据时,将数据调换位置 if i < j: mTemp = arr[j] arr[j] = arr[i] arr[i] = mTemp # 继续往下循环找到所有的符合条件的并调换位置 # 到这里当前基准循环完毕,将当前基准和结束循环的位置数调换,使得基准左边都是小于基准的数,右边都是大于基准的数 arr[left] = arr[i] arr[i] = temp # 继续将基准两边的数进行以上操作 quit_sort(arr, left, j-1) quit_sort(arr, j+1, right)
运行:
# 定义一个列表 arr = [2, 3, 1, 5, 10, 6, 3, 4, 8] print(arr) quit_sort(arr, 0, len(arr) - 1) print(arr)
打印结果:
[2, 3, 1, 5, 10, 6, 3, 4, 8]
[1, 2, 3, 3, 4, 5, 6, 8, 10] -
Python实现快速排序算法
2018-09-18 19:17:27快速排序也是使用了分治思想的排序方法,但与归并排序不一样的是“分”的时候的依据。归并排序“分”的依据是对半分,不管大小,而快速排序则是选定数组中的一个值,以这个值为依据,将数组分为三个部分:小于这个值...快速排序也是使用了分治思想的排序方法,但与归并排序不一样的是“分”的时候的依据。归并排序“分”的依据是对半分,不管大小,而快速排序则是选定数组中的一个值,以这个值为依据,将数组分为三个部分:小于这个值的部分,大于等于这个值的部分,这个值。这样就以选定的点将数组分为两部分(小于值的部分,大于等于值的部分),然后再通过迭代对这两个部分分别继续执行这样一个“分”的过程,直至最后只剩下1-2个元素,即无法再“分”时,此时数组也排序完成。
下面以图示的方法展示一下第一次“分”的过程。
首先给出要排序的数组 l = [ 2 , 8 , 7 , 1 , 3 , 5 , 6 , 4 ] l=[2,8,7,1,3,5,6,4] l=[2,8,7,1,3,5,6,4], s t a sta sta和 e n d end end分别为数组的首尾下标。利用 i i i和 j j j这两个数进行迭代。令 i = s t a − 1 , j = s t a i=sta-1,j=sta i=sta−1,j=sta。
迭代过程中分成了这样几个部分:
i i i所在的位置是 < e n d <end <end的最新的一个值,在“分”的最后,将返回 i + 1 i+1 i+1,即用来比较的值的位置,以供下次迭代。
具体的python代码实现如下。#将数组分为两部分 def partition(l0,sta,end): i=sta-1 for j in range(sta,end): if l0[j]<l0[end]: i=i+1 #如果j所在的位置的值小于end,则i往前进一步,并与j的值交换,即将一个新的值加入到<end的区域 x=l0[i] l0[i]=l0[j] l0[j]=x #一次“分”结束,将用于比较的值放在应该在的地方(两个区域的中间) i=i+1 x=l0[i] l0[i]=l0[end] l0[end]=x return i def quicksort(l0,sta,end): #当至少存在两个元素时,才进行接下来的分解 if sta<end: mid=partition(l0,sta,end) #分成的sta—mid-1,mid+1—end两个区域接着进行分解、迭代 quicksort(l0,sta,mid-1) quicksort(l0,mid+1,end) return l0
快速排序的最坏情况,即每次分解时都极其不平衡,分解为 n − 1 n-1 n−1个元素和 0 0 0个元素,这样分解操作的时间复杂度为 Θ ( n ) Θ(n) Θ(n),而对大小为 0 0 0的数组进行迭代会直接返回,时间复杂度可以忽略。这样算法运行时间的递归式为
T ( n ) = T ( n − 1 ) + Θ ( n ) T(n)=T(n-1)+Θ(n) T(n)=T(n−1)+Θ(n)
解为 T ( n ) = Θ ( n 2 ) T(n)=Θ(n^2) T(n)=Θ(n2)
而最好的情况则是每次都对半分,这样算出的时间复杂度为 Θ ( n l g n ) Θ(nlgn) Θ(nlgn)
而即使是每次的划分达到 9 : 1 9:1 9:1这样一个很不平衡的状态,最终算出的时间复杂度也是 Θ ( n l g n ) Θ(nlgn) Θ(nlgn),事实上,即使是 99 : 1 99:1 99:1也是这样的时间复杂度。(结论和推导均来自《算法导论》)
所以快速排序法的期望时间复杂度为 Θ ( n l g n ) Θ(nlgn) Θ(nlgn),是一个优秀的排序算法。 -
用C语言实现快速排序算法
2016-11-04 22:33:13一、快速排序算法(Quicksort) 1. 定义 快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进,采用了一种分治的策略。 2. 基本思想 通过一趟排序将要排序的数据分割成独立的两部分,其中... -
快速排序的算法思想及Python版快速排序的实现示例
2020-09-21 14:28:52快速排序算法来源于分治法的思想策略,这里我们将来为大家简单解析一下快速排序的算法思想及Python版快速排序的实现示例: -
快速排序算法在Java中的实现
2020-08-28 19:28:56主要介绍了快速排序算法在Java中的实现,简单介绍了快速排序的实现原理,分享了两种实现代码,具有一定参考价值,需要的朋友可以了解下。 -
可视化展示快速排序算法实现效果
2020-06-11 14:12:41该源码使用Qt可以可视化展示快速排序算法实现效果,通过可视化的方式和实时显示算法比较和移动的次数,方便初学者理解快速排序算法的时间复杂度和原理 -
Python实现桶排序与快速排序算法结合应用示例
2020-09-21 01:31:02主要介绍了Python实现桶排序与快速排序算法结合应用,结合实例形式分析了Python快速排序及桶排序结合应用的相关实现技巧,需要的朋友可以参考下 -
快速排序算法实现
2014-12-21 17:47:42快速排序算法C语言实现,快排序算法QuickSort.cpp -
实验题8.4 实现快速排序算法
2021-12-02 22:02:04(1)阅读教材中快速排序算法的相关内容; (2)熟悉快速排序算法。 【实验要求】 (1)采用函数调用的方式完成; (2)文件funp8-4.cpp的作用是快速排序的相关运算操作; (3)实验提交必须有完整正确的程序... -
合并排序算法,快速排序算法,递归,分治
2018-11-22 17:35:47实现并验证合并排序算法; Ex2:实现并验证快速排序算法 Ex3:用递归与分治的方法设计并实现寻找第k小元素算法 -
PHP实现快速排序算法
2018-08-18 18:06:14//快速排序算法 //创建数组并打乱数组 $arr = range(1,20); shuffle($arr); function QuickSort($arr = array()) { $size = sizeof($arr); if ($size<=1) { //如果数组大小小于等于1返回该数组 re... -
快速排序算法的java实现
2012-11-24 21:10:54详细解释了快速排序的java实现.里面有代码,还有注释说明 -
快速排序算法
2019-01-11 21:09:08但是这种算法时间复杂度高,当需要排序的元素较多时,程序运行时间很长,因此产生了快速排序算法。该算法的实现可分为以下几步: 1. 在数组中选一个基准数(通常为数组第一个); 2. 将数组中小于基准数的数据移到... -
C++实现希尔、快速、堆排序、归并排序算法
2021-01-21 15:43:38C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。 -
Python快速排序算法实例分析
2020-09-21 00:49:49主要介绍了Python快速排序算法,简单说明了快速排序算法的原理、实现步骤,并结合具体实例分析了Python实现快速排序的相关操作技巧,需要的朋友可以参考下 -
利用双向循环链表实现快速排序算法
2015-11-06 20:15:16利用了双向循环链表实现了快速排序算法 -
十大经典排序算法-快速排序算法详解
2020-06-16 15:53:43快速排序(Quick Sort)是从冒泡排序算法演变而来的,实际上是在冒泡排序基础上的递归分治法。快速排序在每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列... -
图解java实现快速排序算法
2018-02-07 16:53:39冒泡排序算法,解决了桶排序浪费空间的问题,但在算法的执行效率上却牺牲了很多,它的时间复杂度达到了O(N2)。假如我们的计算机每秒钟可以运行10亿次,那么对1亿个数进行排序,桶排序则只需要0.1秒,而冒泡排序则... -
JS排序算法之希尔排序与快速排序实现方法
2020-10-18 22:18:19主要介绍了JS排序算法之希尔排序与快速排序实现方法,结合实例形式分析了希尔排序与快速排序的原理及javascript实现技巧,需要的朋友可以参考下