交换类排序-----快速排序

水深无声 2022-05-03 01:56 171阅读 0赞

//快速排序
    # include<stdio.h>//时间复杂度 O(nlogn)  不稳定 
    void QuickSort(int a[], int n){
    	int low, high, p, t;
    	if(n < 2)//只有一个数，不用交换 
    	return;
    	p = a[n/2]; //p取数组a的中间的数
    	for(low = 0, high = n-1;; low++, high--){      //从p的两边开始排序
    	    while(p > a[low])                          //将小于p的数放在左边，大于p的数放在p的右边 
    	    low++;                                    
    	    while(p < a[high])
    	    high--;
    	    if(low >= high) break;
    	    t = a[low]; //如果p左边的数比p右边的那个数大，把p左右两边数交换一下 
    	    a[low] = a[high];
    	    a[high] = t;  
    	} 
    	QuickSort(a, low); //第一个递归调用处理数组的前部分，a对应的是数组的首地址，low是指对应的元素个数
    	QuickSort(a+low, n-low);//第二个递归调用处理数组后部分，a + low指的当然是首地址加偏移地址,n-low就是p后面剩下的元素个数		 
    } 
    
    
    int main(){
    	int n;
    	printf("请输入你要排序的数的个数:"); 
    	scanf("%d", &n);
    	int *a = new int[n];//申请一个整型变量空间,没有赋初值，并定义一个整型指针a指向该地址空间 
    	for(int i = 0; i < n; i++)
    	scanf("%d", &a[i]);
    	QuickSort(a, n);
    	printf("排序后:"); 
    	for(int j = 0; j < n; j++)
    	printf("%6d", a[j]);
    	delete []a;//回收数组a的空间 
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】【排序】【交换类】快速排序QuickSort

include<stdio.h> //快速排序 int main(){ int a[]={ 2,1

蔚落/ 2023年10月10日 09:36/ 0 赞/ 58 阅读

相关交换排序之快速排序

快速排序的核心思想： 1. 每一轮选取一个随机的数字作为参照，一般选取本轮的第一个数字，然后设置两个指针，分别指向序列头部和尾部； 2. 与参照数字作比较，左边遇到大

逃离我推掉我的手/ 2023年07月18日 02:49/ 0 赞/ 11 阅读

相关排序算法~交换类排序

交换类排序 [本文是上一篇文章的后续,详情点击该链接~][Link 1] 在上一期我们学习了插入类排序的算法后,知道了排序的一些基本的原理。然而实际上

旧城等待，/ 2022年12月02日 15:21/ 0 赞/ 117 阅读

相关交换排序(冒泡排序、快速排序)

1、冒泡排序 1.1、概念冒泡排序是通过对排序序列从前向后(从下标较小的元素开始)、依次比较相邻元素的值，若发现逆序则交换，使较大的元素逐渐从前移向后部，就像水底

雨点打透心脏的1/2处/ 2022年11月27日 15:45/ 0 赞/ 206 阅读

相关交换排序：快速排序

快速排序（Quicksort）是对冒泡排序算法的一种改进。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成

分手后的思念是犯贱/ 2022年10月16日 02:59/ 0 赞/ 183 阅读

相关交换类排序-----快速排序

//快速排序 include<stdio.h>//时间复杂度 O(nlogn) 不稳定 void QuickSort(int a[], int n

水深无声/ 2022年05月03日 01:56/ 0 赞/ 172 阅读

相关交换类排序-----冒泡排序

冒泡排序： //冒泡排序 include<stdio.h>//时间复杂度 O(n^2) 稳定 void BubbleSort(int a[], i

た入场券/ 2022年05月03日 01:56/ 0 赞/ 228 阅读

相关交换排序——快速排序

/ 算法思想：在待排序元素中选定一个作为中间数，使该数据表中的其他元素的关键字与“中间数” 的关键字相比较，将整个数据表划分成为

电玩女神/ 2022年03月20日 02:54/ 0 赞/ 215 阅读

相关排序 - 交换排序 [2 -- 快速排序]

“傻文，如果你也跟我一样没有耐性，看我的文章吧，专为没有耐性的朋友准备” 研究了几天这个快速排序的算法，可能我比较笨，断断续续加起来估计超过5个小时的时间

雨点打透心脏的1/2处/ 2022年01月12日 15:59/ 0 赞/ 230 阅读

相关排序——交换类排序

冒泡排序 > 算法思想：数组中第一个元素和第二个元素比较，按照规则进行交换，再让第二个和第三个进行比较，直到最大或最小的那个数交换到最后，一趟冒泡排序完成。以升序为例，冒

蔚落/ 2021年11月11日 07:52/ 0 赞/ 322 阅读