精华内容
下载资源
问答
  • 对n个关键字做快速排序
    千次阅读
    2018-12-06 20:06:16
    /*2018.11
    *数据结构与算法-第8章习题T3算法设计题
    *(4)编写算法,对n个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录排在关键字为非负值的记录之前
    *要求:1.采用顺序存储结构,至多使用一个记录的辅助存储空间;
          2.算法的时间复杂度为o(n)(即使用快速排序)
    */
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    typedef int elemtype;
    
    typedef struct
    {
    	elemtype *elem;
    	int length;
    }Sqlist;
    
    void initList(Sqlist &list,int n)/*创建顺序存储数组*/
    {
    	list.elem=new int[n+1];
    	if(!list.elem)
    		return;
    	list.length=n;
    }
    
    void ListInsert(Sqlist &list,int i,int num)/*插入数据*/
    {
    	if(i<1)return;
    	list.elem[i]=num;
    }
    
    void outputList(Sqlist list)/*输出顺序存储的数组*/
    {
    	for(int i=1;i<=list.length;i++)
    	{
    		printf("%4d",list.elem[i]);
    		if(i%10==0)
    			printf("\n");
    	}
    	printf("\n");
    }
    
    int partition(Sqlist &list,int low,int high)/*排序函数1*/
    {
    	elemtype temp;
    	list.elem[0]=list.elem[low];
    	temp=list.elem[low];
    	while(low<high)
    	{
    		while(low<high && list.elem[high]>=temp)
    			--high;
    		list.elem[low]=list.elem[high];
    		while(low<high && list.elem[low]<=temp)
    			++low;
    		list.elem[high]=list.elem[low];
    	}
    	list.elem[low]=list.elem[0];
    	return low;
    }
    
    void qsort(Sqlist &list,int low,int high)/*排序函数2*/
    {
    	int mid;
    	if(low<high)
    	{
    		mid=partition(list,low,high);
    		qsort(list,low,mid-1);
    		qsort(list,mid+1,high);
    	}
    }
    
    void quicksort(Sqlist &list)/*快速排序*/
    {
    	qsort(list,1,list.length);
    }
    
    int main()/*主函数*/
    {
    	Sqlist list1;
    
    	int num,input;
    	printf("请输入需要输入的数的个数:");
    	scanf("%d",&num);
    
    	if(num!=0)
    	{
    		initList(list1,num);
    		printf("请输入需要输入的数据:\n");
    		for(int i=1;i<=num;i++)
    		{
    			scanf("%d",&input);
    			ListInsert(list1,i,input);
    		}
    	
    		printf("\nBefore sorted:\n");
    		outputList(list1);
    		quicksort(list1);
    		printf("After sorted:\n");
    		outputList(list1);
    	}
    	else
    		printf("\n输入的个数为0!\n");
    	return 0;
    }
    
    更多相关内容
  • Array.prototype.quickSort = function() { const rec =(arr) =>{ if(arr.length === 1){return arr} ... // 设置一基准 const mid = arr[0] //进行分区 for(let i =1; i<arr.length; i+...

     

    Array.prototype.quickSort = function() {
    		const rec =(arr) =>{
    			if(arr.length === 1){return arr}
    			// 分别存放 前后的数组
    		   const left = []
    		   const right = []
    		   // 设置一个基准
    		   const mid = arr[0]
    		   //进行分区
    		   for(let i =1; i<arr.length; i+=1){
    			   if(arr[i] < mid){
    				   left.push(arr[i])
    			   }else{
    				   right.push(arr[i])
    			   }
    		   }
    		   
    		   return [...rec(left),mid,...rec(right)] //...用于取出参数对象中的所有可遍历属性,拷贝到当前对象之中
    		}
    		const res = rec(this)
    		res.forEach((n,i)=>{this[i] = n})
    	}
    	const arr = [ 5,4,3,2,1,6,9,8,7]
    	arr.quickSort()
    	console.log(arr)

    快速排序的空间复杂度是多少?

    主要是递归造成的栈空间的使用,最好情况,递归树的深度为 log2​n

    空间复杂度也就为 O(logn)

    最坏情况

    需要进行n‐1递归调用,其空间复杂度为O(n),

    平均情况,

    空间复杂度也为O(logn)。

    时间复杂度的最好最坏的情况是多少,有哪些优化方案?

    在最优的情况下

    快速排序算法的时间复杂度为O(nlogn)。

    最坏的情况

    待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个记录的子序列,注意另一个为空。如果递归树画出来,它就是一棵斜树

    此时需要执行n‐1次递归调用,且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录,也就是枢轴的位置,因此比较次数为

    img

    最终其时间复杂度为O(n^2)。

    时间复杂度优化:
    使用三者取中的方法可以有效降低最坏情况下的时间复杂度。
    三者取中的意思,就是将枢轴的值设置为 A[low] 、A[(low + high)/2] 、A[high] 中的中间值。

     

     

     

    ======================== 

    只是整理 不确定回答的对不对

     

     

     

    展开全文
  • 快速排序

    万次阅读 多人点赞 2018-11-10 23:35:37
    快速排序(Quick Sort)是冒泡排序的一种改进,基本思想是选取一数作为关键字,经过一趟排序,将整段序列分为两部分,其中一部分的值都小于关键字,另一部分都大关键字。然后继续这两部分继续进行排序,从而使...

    快速排序(Quick Sort)是对冒泡排序的一种改进,基本思想是选取一个数作为关键字,经过一趟排序,将整段序列分为两个部分,其中一部分的值都小于关键字,另一部分都大关键字。然后继续对这两部分继续进行排序,从而使整个序列达到有序。
    递归实现:

    void QuickSort(int* arr, int left, int right)
    {
    	int mid = 0;
    	if(left >= right)//表示完成一组的排序
    		return;
    	mid = PartSort1(arr, left, right);关键字的位置
    	QuickSort(arr, left, mid-1);
    	QuickSort(arr, mid+1, right);
    }
    

    PartSort()函数是进行一次快排的算法。
    对于PartSort的函数有很多,这里展示三种。

    左右指针法

    1、选取一个关键字(key),一般取整组记录的第一个数/最后一个,这里采用选取数组的第一个数为key。
    2、设置两个变量left = 0;right = N - 1;
    3、从left一直向后走,直到找到一个大于key的值,right从后至前,直至找到一个小于key的值,然后交换这两个数。
    4、重复第三步,一直往后找,直到left和right相遇,这时将key放置left的位置即可。
    

    在这里插入图片描述
    根据上面的思想,可以写出下面的代码

    int PartSort1(int* arr, int left, int right)
    {
    	int key;
    	int start = left;
    	key = arr[left];
    	while(left < right)
    	{
    		while(left < right && arr[right] >= key)
    		{
    			right--;
    		}
    		while(left < right && arr[left] <= key)
    		{
    			left++;
    		}
    		
    		Swap(&arr[left], &arr[right]);
    	}
    	Swap(&arr[left], &arr[start]);
    	return left;
    }
    

    挖坑法

    1、选取一个关键字key,一般取整组记录的第一个数/最后一个,这里采用选取数组第一个元素key,也是初始的坑位。
    2、设置两个变量left = 0;right = N - 1;
    3、right一直向前走,直到找到一个小于key的值,然后将该数放入坑中,坑位变成了arr[right]。
    4、left一直向前走,直到找到一个小于key的值,然后将该数放入坑中,坑位变成了arr[left]。
    5、重复3和4的步骤,直到left和right相遇,然后将key放入最后一个坑位。
    

    在这里插入图片描述
    代码如下

    int PartSort2(int* arr, int left, int right)
    {
    	int key = arr[left];
    	while(left < right)
    	{
    		while(left < right && arr[left] >= key)
    		{
    			right--;
    		}
    		arr[left] = arr[right];
    		while(left < right && arr[left] <= key)
    		{
    			left++;
    		}
    		arr[right] = arr[left];	
    	}
    	arr[left] = key;
    	return left;
    }
    

    前后指针法

    1、定义变量prev指向序列的开头,定义变量cur指向prev的后一个位置。
    2、当arr[cur] < key时,cur和prev同时往后走,如果arr[cur]>key,cur往后走,pre留在大于key的数值前一个位置。
    3、当arr[cur]再次 < key时,交换array[cur]和array[pre]。
    简单来说就是,在没找到大于key值前,pre永远紧跟cur,遇到大的两者之间机会拉开差距,中间差的肯定是连续的大于key的值,当再次遇到小于key的值时,交换两个下标对应的值就好了
    

    在这里插入图片描述
    代码如下

    int PartSort3(int* arr, int left, int right)
    {
    	int key = arr[left];
    	int prev = left;
    	int cur = left+1;
    	while(cur <= right)
    	{
    		if(arr[cur] < key && (++prev) != cur)
    		{
    			Swap(&arr[prev], &arr[cur]);
    		}
    		++cur;
    	}
    	Swap(&arr[left], &arr[prev]);
    	return prev;
    }
    

    快排的优化
    首先快排的思想是找一个关键字,然后以关键字为中介线,一遍都小于它,另一边都大于它,然后对两段区间继续划分,那么关键字的选取就很关键。
    1、三数取中法
    上面的代码思想都是直接拿序列的第一个值作为关键字,如果最后这个值刚好是整段序列最大或者最小的值,那么这次划分就是没意义的。
    所以当序列是正序或者逆序时,每次选到的关键字都是没有起到划分的作用。快排的效率会退化。
    所以可以每次在选枢轴时,在序列的第一,中间,最后三个值里面选一个中间值出来作为枢轴,保证每次划分接近均等
    2、小区间优化
    由于是递归程序,每一次递归都要开辟栈帧,当递归到序列里的值不是很多时,我们可以采用直接插入排序来完成,从而避免这些栈帧的消耗。

    整个代码如下:

    //三数取中
    int GetMid(int* arr, int left, int right)
    {
    	int mid = left + ((right-left)>>1);
    	if(arr[left] <= arr[right])
    	{
    		if(arr[mid] < arr[left])
    		{
    			return left;
    		}
    		else if(arr[mid] > arr[right])
    		{
    			return right;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    	else
    	{
    		if(arr[mid] < arr[right])
    		{
    			return right;
    		}
    		else if(arr[mid] > arr[left])
    		{
    			return left;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    
    }
    //左右指针法
    int PartSort1(int* arr, int left, int right)
    {
    	
    	int key;
    	int start = left;
    	int mid = GetMid(arr, left, right);
    	Swap(&arr[mid], &arr[left]);
    	key = arr[left];
    	while(left < right)
    	{
    		while(left < right && arr[right] >= key)
    		{
    			right--;
    		}
    		while(left < right && arr[left] <= key)
    		{
    			left++;
    		}
    		Swap(&arr[left], &arr[right]);
    	}
    	Swap(&arr[left], &arr[start]);
    	return left;
    }
    
    //挖坑法
    int PartSort2(int* arr, int left, int right)
    {
    	int mid = GetMid(arr, left, right);
    	Swap(&arr[left], &arr[mid]);
    	int key = arr[left];
    	
    	while(left < right)
    	{
    		while(left < right && arr[left] >= key)
    		{
    			right--;
    		}
    		arr[left] = arr[right];
    		while(left < right && arr[left] <= key)
    		{
    			left++;
    		}
    		arr[right] = arr[left];	
    	}
    
    	arr[left] = key;
    	return left;
    }
    
    //前后指针法
    int PartSort3(int* arr, int left, int right)
    {
    	int mid = GetMid(arr, left, right);
    	Swap(&arr[left], &arr[mid]);
    	int key = arr[left];
    	int prev = left;
    	int cur = left+1;
    	while(cur <= right)
    	{
    		if(arr[cur] < key && (++prev) != cur)
    		{
    			Swap(&arr[prev], &arr[cur]);
    		}
    		++cur;
    	}
    	Swap(&arr[left], &arr[prev]);
    	return prev;
    }
    void QuickSort(int* arr, int left, int right)
    {
    	int mid = 0;
    	if(left >= right)
    		return;
    	//小区间优化
    	if((right - left) <= 5)
    	{
    		InsertSort(arr, right-left+1);
    	}
    	mid = PartSort3(arr, left, right);
    	QuickSort(arr, left, mid-1);
    	QuickSort(arr, mid+1, right);
    }
    

    非递归实现
    递归的算法主要是在划分子区间,如果要非递归实现快排,只要使用一个栈来保存区间就可以了。
    一般将递归程序改成非递归首先想到的就是使用栈,因为递归本身就是一个压栈的过程。

    void QuickSortNoR(int* arr, int left, int right)
    {
    	
    	int mid = 0;
    	int begin,end;
    	Stack s;
    	StackInit(&s, 3);
    	StackPush(&s, right);
    	StackPush(&s,left);
    	while(StackEmpty(&s) != 0)
    	{
    		begin = StackTop(&s);//取出左边区间
    		StackPop(&s);
    		end = StackTop(&s);//起初右边区间
    		StackPop(&s);
    		mid = PartSort1(arr, begin, end);
    		if((mid+1) < right)
    		{
    			StackPush(&s, right);
    			StackPush(&s,mid+1);
    		}
    		if((mid-1) > left)
    		{
    			StackPush(&s, mid-1);
    			StackPush(&s, left);
    		}
    	}
    }
    
    
    展开全文
  • 关键字排序。c++

    千次阅读 2020-02-25 18:20:12
    基于多关键字排序/基数排序的长方形排列。

    多关键字排序

    一个长方形有长和宽,分别设为 a 和 b,现在想对一些长方形进行排序。
    有一种新的排序方法。如下:
    我们按照两个长方形的a-b值来对他们按降序排序,如果有重复,按照b值升序排序,如果还有重复,按照输入的顺序排序。

    也就是说,是多关键字排序:

    第1关键字,a-b,降序;

    第2关键字,b,升序;

    第3关键字,输入的顺序,升序;

    输入有多组测试数据(大概100组),每一组测试数据第一行先给出一个整数n,代表有n个长方形需要被排序。
    长方形被从0到n−1标号。
    接下来n行,每一含有两个整数代表每一个长方形a和b
    第i行描述长方形i−1的信息。
    处理到文件末尾。
    所有整数都在[1,100]的范围内。
    对于每一个数据,在一行中输出排好序之后的长方形ID,注意每两个 ID 【之间!】有一个空格,其他地方不要有多余空格

    sample input:
    2
    100 1
    1 2
    3
    100 50
    3 4
    1 2

    sample output:
    0 1
    0 2 1

    思路:
    定义结构体,里面存储对应长方形的三个关键字。
    注意题目中多组测试数据的输入方法。
    对于多关键字排序,也就是基数排序,需要编写对应的cmp函数。
    注意sort函数的用法:sort(begin,end,compare)

    #include<iostream>
    #include<string>
    #include<algorithm>
    using namespace std;
    struct code
    {
    	int x,y;//长宽
    	int a;//a=x-y;
    	int i;//i顺序,第三关键字 
    }arr[10000];
    bool compare(code m,code n)
    {
    	if(m.a!=n.a)	return m.a>n.a;
    	if(m.y!=n.y)	return m.y<n.y;
    	return m.i<n.i;
    }
    int main()
    {
    	int n;
    	while(scanf("%d",&n)!=EOF)
    	{
    		for(int i=0;i<n;i++)
    		{
    			int w,e;
    			cin>>w>>e;
    
    				arr[i].x=w;
    				arr[i].y=e;
    				arr[i].a=arr[i].x-arr[i].y;
    				arr[i].i=i;
    		}
    		sort(arr,arr+n,compare);
    		for(int i=0;i<n-1;i++) cout<<arr[i].i<<" ";
    		printf("%d\n",arr[n-1].i);
    	}
    	return 0;
    }
    展开全文
  • 然后序列前n-1元素进行第二次冒泡,将倒数第二选出。以此类推直到所有被选出,冒泡结束。 通过分析可以得出,冒泡排序的时间复杂度为O(n2)。 快速排序冒泡排序的一种改进,它是处理大数据集最快的排序之...
  • 用函数实现快速排序,并输出每次分区后排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一空格分隔 Sample Input ...
  • Golang实现快速排序

    2021-04-22 21:15:27
    当本次排序完成后,关键字将会移至正确的位置,数组被分为两更小的子数组,以子数组为初始数组,接着重复以上操作。 二、代码 package main import "fmt" func QuickSort(data []int, low int, high int) { if ...
  • 3. 快速排序

    2021-07-28 05:22:15
    由于关键字的比较和交换是跳跃进行的,因此,快速排序是一种不稳定的排序方法。0. 序1. 冒泡排序2. 快速排序2.1基本思想2.2一趟快速排序(一趟划分)2.3过程2.4实现2.5复杂度分析2.5.1时间复杂度(包含证明)2.5.2空间...
  • 数据结构 作业答案 第8章 排序

    千次阅读 2020-06-14 18:19:25
    第8章 排序 1.选择题 (1)从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置上的方法,这种排序方法称为( )。...(3)对n个不同的关键字由小到大进行冒泡排
  • 快速排序 冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序。使用的是递归原理,在所有同数量级O(n longn) 的排序方法中,其平均性能最好。就平均时间而言,是目前被认为最好的一种内部...
  • 关键字快速排序

    2016-02-05 16:03:00
    快排双关键字 1 var 2 i,j,l,m,n:longint; 3 a,b:array[0..10000]of longint; 4 procedure px(l,r:longint); 5 var 6 i,j,k,m,x,y:longint; 7 begin 8 i:=l; 9 j:=r; 10 x:=a[(i+j) div 2];...
  • 数据结构--排序之快速排序

    千次阅读 多人点赞 2022-02-08 20:09:50
    快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有...
  • 数据结构 八大排序之快速排序

    千次阅读 2022-04-29 21:13:53
    数据结构 八大排序之快速排序 1.1快速排序引入 1.2快速排序的基本思想 1.3快速排序的排序流程 1.4实例说明 1.5代码实现 1.6性能分析
  • 快速排序的基本思想是:通过一趟排序将待排记录分割成独立的俩部分,其中一部分记录的关键字比另一部分记录的关键字小,则可分别这俩部分记录继续进行排序,以达到整个序列有序的目的,快速排序的时间性能取决于...
  • 交换,指的是根据序列中两个关键字的比较结果来对换这两记录在序列中的位置,主要有冒泡排序与快速排序。 冒泡排序(Bubble Sort) 冒泡排序的基本思想:从前往后或者从后往前,相邻的两元素进行比较,若逆序...
  • 1、常见排序算法实现(1-6选择几算法练习) ... (4)实现快速排序算法。 (5)实现堆排序算法。 (6)合并排序算法。 2) 实现提示: 数据输入后,每选择一种算法,把数据拷贝后再排序,保证原始数据不破坏.
  • 本节内容 快速排序 王道考研/ 知识总览 基于交换的排序根据序列中两元素关键字的较结果来对换这两记录在序列中的位置 王道考研/ 快速排序 49 38 65 97 76 13 27 49 0 1 2 3 4 5 6 7 算法思想在待排序表L[1n]中任...
  • 只有C中的qsort存在,调用比较麻烦,其实在数据结构中,快速排序法是经典排序之一,上网搜了一下简介,把对应的VC程序改了一下,成了下面的matlab代码:%快速排序法%基本的思想:通过一趟排序将待排的记录分割成...
  • 数据结构 — 快速排序

    千次阅读 2017-08-30 17:22:48
    快速排序 基本思想   快速排序
  • 快速排序算法

    万次阅读 多人点赞 2021-01-11 13:37:49
    文章目录一、快速排序概述1.1 什么是快速排序1.2 快速排序过程解析二、快速排序的具体步骤三、快速排序的代码实现 一、快速排序概述 1.1 什么是快速排序 快速排序(Quick Sort)是冒泡排序的一种改进。它的基本...
  • 假设含n个记录的序列为{ R1, R2, …, Rn }其相应的关键字序列为 { K1,K2, …,Kn }。经过排序确定一种排列{ Rp1≤Rp2≤…≤Rpn},使得它们的关键码满足如下递增或递减的关系 Kp1≤ Kp2 ≤…≤ Kp...
  • 【数据结构】第七章 排序

    千次阅读 2020-04-14 15:54:00
    1.排序基本概念 1.拓扑排序是将有向图中所有结点排成一线性序列...任意n个关键字排序的比较次数至少为⌈log2(n!)⌉\lceil log_2(n!) \rceil⌈log2​(n!)⌉ 任意7个关键字进行基于比较的排序,至少要进行几次...
  • . . 数据结构实验课程最终报告 题 目实验八快速排序 专业班级计算机科学与技术 姓 名XXX ...假设含n个记录的序列为{ R1, R2, Rn } 其相应的关键字序列为 { K1, K2, Kn } 这些关键字相互之间可以进行比较即在它们之间存
  • 我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度,可以用递归树来描述递归算法的执行情况。...在最优情况下,Partition每次都划分得很均匀,如果排序n个关键字,其递归树的深度就...
  • 《数据结构》-第八章 排序(习题)

    千次阅读 2021-08-28 22:20:18
    堆排序、快速排序和归并排序是本章的重难点,应深入掌握各种排序算法的思想、排序过程(能动手模拟)和特征(初态的影响、复杂度、稳定性、适用性等)。 本章同样作为考察重点章节,通常以选择题的形式考查不同算法...
  • 快速排序:每一趟排序过程将待排序序列根据关键字大小排序分割成两部分,第一部分的所有数据值小于关键字,第二部分的所有数据值大于等于关键字.然后再依次分割后的每部分再次使用快速排序进行排序。 ...
  • 基于关键词比较的排序(C++版): 插入排序 直接插入、希尔排序;交换排序 冒泡排序、快速排序;选择排序 直接选择、堆排序;合并排序
  • ❤️全面图解快速排序,详细图文并茂解析!❤️

    千次阅读 多人点赞 2021-08-22 14:11:02
    通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别这两部分记录继续进行排序,以达到整个序列有序。主要采用分治法和挖坑填数等方法,分治法就是大问题分解成...
  • C/C++快速排序及优化详解

    万次阅读 2018-04-14 12:20:54
    一、快速排序原理快速排序是一种基于分治思想的排序算法。在快排中,我们的工作主要集中在划分而不是合并子问题。首先我们要选择一中轴,把比中轴大的元素放在它的右边,比他小的放在它的左边。中轴的选择有很多种...
  • 快速排序终于要来了,快速排序也是交换排序的一种,其实讲快速排序前应该先讲讲冒泡排序,因为快速排序冒泡排序的一种改进,那就先来用最快速度复习一下冒泡排序: 冒泡排序:假设要对待排序了升序排序,那么...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 88,219
精华内容 35,287
热门标签
关键字:

对n个关键字做快速排序