精华内容
下载资源
问答
  • 快速排序算法是在几种排序算法中效率最高的一个排序算法了,故称为快速排序,它的时间复杂度为:O(nlog2n),相比冒泡排序算法的O(n2)有很大的提升。

    前言

    哈喽,大家好,我最近在复习数据结构中的排序算法章节,今天复习到了交换排序算法中的快速排序算法,所以给大家分享一下。

    一、什么是快速排序?

    快速排序算法是在几种排序算法中效率最高的一个排序算法了,故称为快速排序,它的时间复杂度为:O(nlog2n),相比冒泡排序算法的O(n2)有很大的提升。

    二、算法思想

    1、选取一个基准元素(一般我们将待排序序列中的第一个元素选取为基准元素)
    2、将其他元素与基准元素进行比较,比基准元素大的放到基准元素的右边,比基准元素小的放到基准元素的右边。(以基准元素为中心将元素重新分成两个序列并返回基准元素的下标
    3、将新生成的两个序列继续执行1和2两步(此处可以用递归实现)

    接下来我们通过一个动图来看一下快速排序算法。
    快速排序

    三、实例讲解

    我们有一个待排序序列是:【 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】
    在这里插入图片描述

    第一轮排序:

    ①选取第一个元素44为基准坐标。
    在这里插入图片描述

    ②以44为中心,将序列分为两部分,左边比44小,右边比44大。
    在这里插入图片描述
    ③原来的序列被分成两部分,一部分比44小的是【0,基准坐标-1】,另一部分比44大的是【基准坐标+1,最后】,将这两部分继续执行①和②两步最终即可排序完成。

    第一轮排序总结: 算法思想其实不难理解,那么接下来需要解决的问题就是,如何将一个序列以基准坐标分成相对有序的两部分,以及递归出口问题。

    四、算法分析

    1.时间复杂度

    O(nlog2n)

    2.空间复杂度

    空间复杂度由于需要开辟一个临时空间来存储基准坐标所以是:O(1)

    五、代码实现

    #include<stdio.h>
    void Print(int array[],int len){
    	for(int i=0;i<len;i++){
    		printf("%d ",array[i]);
    	}
    	printf("\n");
    } 
    /*获取基准坐标,并相对有序(左边比基准坐标小,右边比基准坐标大)*/
    int getStandard(int array[],int low,int high) {
    	int key = array[low];  //临时保存基准元素 
    	while(low<high) {  
    		//high指针从后向前遍历 , 元素比基准元素大则指针向前移动 则比基准元素小则和基准元素交换 
    		while(low<high && array[high]>=key){
    			high--;
    		}
    		if(low<high){
    			array[low] = array[high];  //赋值给第一个元素,因为第一个元素作为基准元素已经临时保存了,所可以直接赋值 
    		}
    		//low指针从前向后遍历 , 元素比基准元素小则指针向后移动 否则比基准元素大则和基准元素交换 
    		while(low<high && array[low]<=key){
    			low++;
    		}
    		if(low<high){
    			array[high] = array[low];  //复制给high指针所指得位置,因为在11行已经赋值给array[low]了 
    		}
    	}
    	array[low] = key;
    	return low; 
    }
    void QuickSort(int array[],int low,int high){
    	if(low<high){  //递归出口 
    		int standard = getStandard(array,low,high);
    		QuickSort(array,low,standard-1);  //比基准元素小的部分继续调用快速排序 
    		QuickSort(array,standard+1,high);   //比基准元素大的部分继续调用快速排序 
    	}
    }
     int main(){
     	int array[] = {3, 44, 38, 5, 47, 15, 36};
    	int size = sizeof(array) / sizeof(int);
    	printf("原始序列为:\n");
    	Print(array,size); 
    	QuickSort(array,0,size-1);
    	printf("排序后序列为:\n");
    	Print(array,size); 
     } 
    

    六、运行结果

    在这里插入图片描述

    总结

    最后,我们只需要记住快速排序的算法思想(两步)以及如何通过两个指针来实现将待排序序列分成两部分即可。

    展开全文
  • C语言交换法排序

    千次阅读 2020-12-27 14:10:33
    2交换法排序(10分) 题目内容: 从键盘输入n个(n≤10)整数,用交换法进行排序(非递减有序),结果输出排序后的序列。说明:交换法排序用函数实现,函数原型为:void sort(int *a,int n); 交换法排序的基本思想是...

    交换法排序
    题目内容:

    从键盘输入n个(n≤10)整数,用交换法进行排序(非递减有序),结果输出排序后的序列。说明:交换法排序用函数实现,函数原型为:void sort(int *a,int n); 交换法排序的基本思想是:n个元素共需要n-1趟,其中第i(从0变化至n-2)趟的任务是找出本趟中最小的元素放在下标为i的位置上,每趟通过从i+1到n-1下标的元素逐个与i下标元素比较及时交换进行排序。

    #include <stdio.h>
    void shuru(int a[], int n)
    {
    	int i;
    	for (i = 0; i < n; i++)
    		scanf("%d", &a[i]);
    }
    
    
    void da(int z[],int n)
    {
    	int x, c, temp, i;
    	for (x = 0; x < n; x++)
    		for (c = 0; c < n - 1; c++)
    		{
    			if (z[c] > z[c + 1])
    			{
    				temp = z[c + 1];
    				z[c + 1] = z[c];
    				z[c] = temp;
    			}
    		}
    	for (i = 0; i < n; i++)
    		printf("%d  ", z[i]);
    	printf("\n");
    }
    int main()
    {
    	int n;
    	int a[10];
    	scanf("%d", &n);
    	shuru(a, n);
    	da(a, n);
    }
    
    展开全文
  • 交换排序 1.冒泡排序 算法思想:假定无序序列长为len,从前往后两两比较相邻元素的值,若为逆序(a[i] > a[i+1]),则交换它们,直到序列比较完。这就是一趟冒泡,下一趟冒泡时,前一趟确定的最小元素不再参与...

    交换排序

    1.冒泡排序

    算法思想:假定无序序列长为len,从前往后两两比较相邻元素的值,若为逆序(a[i] > a[i+1]),则交换它们,直到序列比较完。这就是一趟冒泡,下一趟冒泡时,前一趟确定的最小元素不再参与比较,待排序列减少一个元素,每趟冒泡的结果就是把序列中的最小元素放在最终位置,最多需要len-1趟冒泡就可以排好序。
    C语言代码:

    #include<stdio.h>
    #include<string.h>
    #define len 5
    void swap(int &a, int &b)
    {
    	int temp;
    	temp = a;
    	a = b;
    	b = temp;
    }
    
    //冒泡排序 时间复杂度O(n^2) 空间复杂度O(1)  
    void bubbleSort(int a[])
    {
    	int i,j,flag;
    	for(i=0;i<len;i++)
    	{
    		//表示本趟冒泡是否发生交换标志
    		flag = 0;
    		for(j=0;j<len-i-1;j++)
    		{
    			if (a[j] > a[j+1])
    			{
    				flag = 1;
    				//交换
    				swap(a[j], a[j+1]);		
    			}		
    		}		
    		//本趟遍历没有发生交换,说明表已经有序
    		if(flag == 0)
    		{
    			break;
    		}
    	}		
    } 
    int main()
    {
    	int a[] = {45,14,27,71,12};
    	int i;
    	printf("未排序前:\n"); 
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    	printf("\n经过排序后:\n"); 
    	bubbleSort(a);
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    }
    

    2、快速排序

    算法思想:在无序序列中任取一个元素作为基准(通常情况下选择第一个元素)。然后对无序序列分区,比基准元素大的放在它的右边,比它小的放在左边,对左右两个分区进行递归处理直到所有元素都变成有序。

    C语言代码:

    #include<stdio.h>
    #include<string.h>
    #define len 5
    //快速排序分区间函数
    int partition(int a[], int low, int high)
    {
    	//将当前表第一个元素设为基准值,对表进行划分
    	int pivot = a[low];
    	//循环跳出条件
    	while(low < high)
    	{
    		while(low<high && a[high] >= pivot)
    			--high;
    		//比基准值小的值移动到左端
    		a[low] = a[high];
    		while(low<high && a[low] <= pivot)
    			++low;
    		//比基准值大的值移动到右端
    		a[high] = a[low];
    	}
    	//基准元素放到最终位置
    	a[low]= pivot;
    	//返回存放基准值的最终位置下标
    	return low;
    } 
    void quickSort(int a[], int low, int high)
    {
    	//递归跳出的条件
    	if(low<high)
    	{
    		//将数组a划分为两个子数组
    		int part = partition(a, low, high);
    		//依次对两个子表进行递归排序
    		quickSort(a, low, part-1);
    		quickSort(a, part+1, high);
    	}
    }
    int main()
    {
    	int a[] = {45,14,27,71,12};
    	int i;
    	printf("未排序前:\n"); 
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    	printf("\n经过排序后:\n"); 
    	quickSort(a, 0, len);
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    }
    
    展开全文
  • 3.交换法排序 #include<stdio.h> //头文件 int main(){//主函数 int i, j, n; int a[999]; int iTemp; //输入 printf("请输入需要排序的元素的个数:\n"); scanf("%d", &n); printf("请输入需要...

    3.交换法排序

    #include<stdio.h> //头文件 
    int main(){//主函数 
    	int i, j, n;
    	int a[999];
    	int iTemp;
    	//输入 
    	printf("请输入需要排序的元素的个数:\n");
    	scanf("%d", &n);
    	printf("请输入需要排序的元素:\n");
    	for (i=0; i<n; i++){
    		scanf("%d", &a[i]);
    	} 
    	//排序 
    	for (i=0; i<n-1; i++){
    		for (j=i+1; j<n; j++){
    			if (a[j] < a[i]){//升序 
    				iTemp = a[i];
    				a[i] = a[j];
    				a[j] = iTemp;
    			}
    		}
    	}
    	//输出 
    	for (i=0; i<n; i++){
    		printf("%d\t", a[i]);
    		if(i%4 == 0)
    			printf("\n");
    	}
    	return 0;
    }
    
    展开全文
  • C语言实现冒泡排序 文章目录C语言实现冒泡排序冒泡排序算法项目完整代码运行效果图 冒泡排序算法 //冒泡排序算法 ... //表示本趟冒泡排序是否发生了交换的标志 for (int j = len - 1; j > i; --j)
  • C语言基础:直接交换法排序

    千次阅读 2020-03-23 22:09:43
    思路:对每一个数与其下一个数比较,如果后一个数大于前一个数,则会进行交换,实现排序。 #include<stdio.h> #define N 10 main() { int a[N],i,j,p,t; for(i=0;i<N;i++) scanf("%d",&a[i]); for...
  • C语言实现快速排序 文章目录C语言实现快速排序快速排序算法1.划分操作2.快速排序算法实现项目完整代码运行效果图 快速排序算法 1.划分操作 //划分操作 int Partition(int arr[], int low, int high) { //一趟划分 ...
  • C语言交换排序

    千次阅读 2019-01-25 10:53:18
    由小到大排序 #include&lt;stdio.h&gt; void read(int date[],int n) // 读取需要被排序的数据 { int i ; printf("please input %d dates :",n); for(i=0;i&lt;n;i++) scanf("%d&...
  • C语言交换排序算法

    千次阅读 2018-06-21 16:37:10
    //交换排序算法:外循环len-1次,元素比较n&gt;n+1,则交换元素值,n&gt;n+2则交换元素值 int arry[10]={4,2,1,9,7,3,5,0,8,6}; int i,j, iTemp; for(i=0;i&lt;10-1;i++) { for...
  • C语言基础算法篇-交换排序前言冒泡排序 前言 在这里为C语言经常使用到的排序算法进行归类整理,让初学者和自己更好的理解排序算法。在这里我主要描述排序算法中的交换排序:冒泡排序、快速排序。 交换排序最基本的...
  • 问题:C语言一维数组排序,读入一个正整数 n , 再读入 n 个整数(1<n<=10) 样例: 请输入元素个数:5 请输入 5 个整数: 3 2 1 5 4 排序后:1 2 3 4 5 #include<stdio.h> #include<math.h> int...
  • PAGE / NUMPAGES 选择排序法 选择排序法是从算法优化的角度对冒泡法的改进其改进的思想是经过一轮的两两比较后并不马上交换数的位置而是找到本轮最小的数记下该数的位置即在数组中的下标待本轮比较完毕后通过一次...
  • C语言排序算法之简单交换排序,直接选择排序,冒泡排序,最近考试要用到,网上也有很多... 3 交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动 4 不稳定 5 */ 6 #i...
  • 1.冒泡排序(Bubble Sort): void BubbleSort(int *r) { int i,j; for(i=0;i<Maxsize;i++) for(j=1;j<Maxsize-i;j++) if(r[j-1]>r[j]) Swap(r[j-1],r[j]); } 2.升级版冒泡排序: ...
  • C语言-交换排序

    2021-04-25 23:13:51
    printf("排序前\n"); for(i=0;i<5;i++){ printf("%d\t",arr[i]); } printf("\n\n"); for(i=0;i<5-1;i++){ for(j=i+1;j<5;j++){ if(arr[i]<arr[j]){ t = arr[i]; arr[i] =.
  • c语言基本例题总结】 问题描述 比较交换排序 代码 #include<stdio.h> #define N 10 int main(void){ int i,j,n,t,m,k; int a[N]; printf("请输入元素个数:");... //比较交换排序法 for(i=0;i&
  • 交换排序和选择排序回顾 学习内容: 标题:交换排序:及每次与数组后一位里的数据进行比较,若后一位大于本位里面的数据则进行交换直至对比完整个数组,效率较低。 参考代码 #include<stdio.h> void main(){ ...
  • C语言冒泡排序算法

    千次阅读 多人点赞 2018-12-25 17:05:57
    冒泡排序的概念:冒泡排序(Bubble Sort)是一种简单的交换排序,它是通过两两比较相邻记录的关键字,如果发生逆序就进行交换,从而使关键字小的记录如气泡一般逐渐往上“漂浮”(左移),或者使关键字大的记录如...
  • 交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列前端移动。 1.快速排序 基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据要比另外一部分的所有数据都要...
  • 冒泡排序法C语言实现)

    千次阅读 2019-09-23 10:28:26
    冒泡排序是最简单的排序方法,它的计算次数多,不是最快的,但它是最基本的排序方法。它的原理是: 假设有一个整型数组:2,4,9,1,6,3,5,8,10,7; 要求把它们按从小到大的顺序依此排列。它的实现代码如下: 第一轮...
  • 快速排序法C语言详解

    2014-03-19 15:05:28
    位置不一定是它此轮排序的最终位置,所以整个数组拉通交换排序,所以,j除了最左边一个元素外,数组其它元素都要访问, 所以必须是j>left。 j>=left, 也能实现功能,但是,j>left,少循环一次,...
  • 冒泡排序法c语言

    千次阅读 2019-03-10 15:29:54
    冒泡排序法 排序过程: (1)比较第一个数与第二个数,若为逆序a[0]&gt;a[1],则交换;然后比较第二个数与第三个数;依次类推,直至第n-1个数和第n个数比较为止——第一趟冒泡排序,结果最大的数被安置在最后一...
  • 交换排序 基本思想: 两两比较,如果发生逆置则交换,直到所有记录都排好序为止。 常见的交换排序 1.冒泡排序 O(n2) 2.快速排序 O(nlog2n)
  • 第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在
  • ZQ 选择排序法 选择排序法是从算法优化地角度对冒泡法地改进其改进地思想是经过一轮地两两比较后并不马上交 换数地位置而是找到本轮最小地数记下该数地位置即在数组中地下标待本轮比较完毕后通过 一次交换即可将本轮...
  • C语言交换法排序

    2011-10-04 22:28:02
    程序已验证,100%可运行,欢迎下载 程序已验证,100%可运行,欢迎下载
  • 选择法排序 选择法排序是指:如果要把一个数组从小到大排列,那么就从该数组中依次选择最小的数字来排序。从第一个数字开始,将第一个数字与数组中剩下数字中最小的那一个交换位置,然后将第二个数字与剩下数字中...
  • /* Description:二、交换排序法:冒泡+快排(C语言源代码) /* Date:2021/9/10 /* Author:汝南城 /****************************************************/ #include<stdio.h> #include<stdlib.h> #define...
  • #include<stdio.h> #define n 7 int main() { int i,j; int x[n]; printf("请输入7个数字:\n"); for(i=0;i<...i++) //控制趟次,7个数就需要交换6趟(两两交换),∴ :i<n-1...
  • 简单选择排序(C语言)

    2020-06-18 15:59:39
    简单选择排序 1.排序原理 简单选择排序算法原理:每次从左至右扫描序列,记下最小值的位置。然后将最小值与当前位置的值交换 排序过程 序列:[5 4 3 2 1] 从小到大排列 第一轮:[(5) 4 3 2 1] 当前位置:[5] [4,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,978
精华内容 5,591
关键字:

交换排序法c语言

c语言 订阅