精华内容
下载资源
问答
  • 关键字快速排序

    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];...

    快排双关键字

     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];
    11   y:=b[(i+j) div 2];
    12  repeat
    13   while (a[i]<x)or((a[i]=x)and(b[i]<y)) do inc(i);
    14   while (a[j]>x)or((a[j]=x)and(b[j]>y)) do dec(j);
    15   if i<=j then
    16   begin
    17      k:=a[i];a[i]:=a[j];a[j]:=k;
    18      k:=b[i];b[i]:=b[j];b[j]:=k;
    19     inc(i);
    20     dec(j);
    21    end;
    22   until i>j;
    23   if i<r then px(i,r);
    24   if j>l then px(l,j);
    25 end;
    26  begin
    27  readln(n);
    28  for i:=1 to n do
    29   begin
    30    read(a[i]);
    31    read(b[i]);
    32   end;
    33  px(1,n);
    34  for i:=1 to n do
    35   writeln(a[i],' ',b[i]);
    36 end.

     

    转载于:https://www.cnblogs.com/vacation/p/5183258.html

    展开全文
  • *(4)编写算法,对n个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录排在关键字为非负值的记录之前 *要求:1.采用顺序存储结构,至多使用一记录的辅助存储空间; 2.算法的时间复杂度为o(n)(即使用快速...
    /*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;
    }
    
    展开全文
  • 题目:将所有取负值的关键字放在所有取非负值的关键字之前———-代码参考/* auther :colin 2016.11.27 将所有取负值的关键字放在所有取非负值的关键字之前 */ #include #include #define N 6 void resort(int a[]...

    题目:将所有取负值的关键字放在所有取非负值的关键字之前

    ———-代码参考

    /*
    auther :colin
    2016.11.27
    将所有取负值的关键字放在所有取非负值的关键字之前
    */
    #include <stdio.h>
    #include <stdlib.h>
    #define N 6
    void resort(int a[],int n);
    
    int main()
    {
        int a[N] = {0,-1,6,-3,7,-6};
        printf("将所有取负值的关键字放在所有取非负值的关键字之前:\n");
        resort(a,N);
        int i;
        for(i = 0;i < N;i++){
            printf("%d\n",a[i]);
        }
        return 0;
    }
    
    void resort(int a[],int n)
    {
        int i=0,j=n-1;
        int temp;
        while(i!=j)
        {
            while(i<j&&a[i]<0) i++;
            if(i<j)
            {
                temp = a[i];
            }
            while(i<j&&a[j]>=0)j--;
            if(i<j)
            {
                a[i++] = a[j];
                a[j] = temp;
            }
        }
    }
    

    运行结果:
    这里写图片描述

    展开全文
  • 快速排序的基本思想是:通过一趟排序将待排记录分割成独立的俩部分,其中一部分记录的关键字比另一部分记录的关键字小,则可分别这俩部分记录继续进行排序,以达到整个序列有序的目的,快速排序的时间性能取决于...

    希尔排序相当于直接插入排序的升级,它们同属于插入排序类
    堆排序相当于简单选择排序的升级,它们同属于选择排序类
    快速排序相当于冒泡排序的升级,它们都属于交换排序类

    快速排序的基本思想是:通过一趟排序将待排记录分割成独立的俩部分,其中一部分记录的关键字比另一部分记录的关键字小,则可分别对这俩部分记录继续进行排序,以达到整个序列有序的目的,快速排序的时间性能取决于快速排序递归的深度,快速排序需要选定枢轴,通过一遍排序后将小于枢轴的值放到枢轴的左边,大于的值放到它的右边,这样来看,枢轴的选取就很重要,因为它的值决定了这次排序的效率如何,一般可以采用数组的第一个数据作为枢轴,如果这个数据的值正好在所有数据中处于中间的值,那么效率会很高,如果处于最大值或者最小值,则效率会很低,所以本例采用三数取中法了进行优化

    优化选取枢轴改进方法:三数取中法 即取三个坐标所对应的数据先进行排序,将中间数作为枢轴,一般取左端、右端、和中间三个数。

    #include "stdafx.h"
    #include <stdlib.h>
    #include <time.h>
    #include <iostream>
    #include <set>
    using namespace std;
    
    #define ArrayCount  10
    
    //选组枢轴
    int Partition(int* arr, int left, int right)
    {
    	int m = left + (right - left) / 2; //计算数组中间的元素下标
    	if (arr[left] > arr[right])
    		swap(arr[left], arr[right]);
    	if (arr[m] > arr[right])
    		swap(arr[m], arr[right]);
    	if (arr[m] > arr[left])
    		swap(arr[m], arr[left]);	//保证左端数据为中间值
    	int pivotValue = arr[left];     //将三个数中的中间值作为枢轴
    	while (left < right)
    	{
    		while (left < right&&arr[right] >= pivotValue)
    			right--;
    		swap(arr[left], arr[right]);
    		while (left < right&&arr[left] <= pivotValue)
    			left++;
    		swap(arr[left], arr[right]);
    	}
    	return left;
    }
    
    
    void QuickSort(int* arr, int left, int right)
    {
    	int pivotIndex;  //枢轴所在下标	
    	if (left < right)
    	{
    		pivotIndex = Partition(arr, left, right);	//将arr数组一分为二 选出枢轴并将小于枢轴的值放到它的左边,大于它的值放到右边,并返回这个枢轴
    		QuickSort(arr, left, pivotIndex - 1);		//对低子表递归排序
    		QuickSort(arr, pivotIndex + 1, right);		//对高子表递归排序
    	}
    }
    
    //打印数组
    void PrintArray(int* arr, int arrayCount)
    {
    	for (int i = 0; i < arrayCount; i++)
    		cout << arr[i] << endl;
    }
    
    int main()
    {
    	srand((unsigned)time(NULL));
    	int array[ArrayCount];
    	set<int> s;
    	for (int i = 0; i < ArrayCount; i++)
    	{
    		while (1)  //直到生成了不重复的数据,再往下生成
    		{
    			int number = rand() % ArrayCount;
    			if (s.find(number) == s.end())
    			{
    				s.insert(number);
    				array[i] = number;
    				break;
    			}
    		}
    	}
    	cout << "排序前:" << endl;
    	PrintArray(array, ArrayCount);
    	QuickSort(array, 0, ArrayCount - 1);   //传入的数组的下标
    	cout << "排序后:" << endl;
    	PrintArray(array, ArrayCount);
    	return 0;
    }

     

    展开全文
  • 关键字排序实验

    2018-07-08 00:40:00
    了解多关键字的使用范围,并实现牌照按多关键字排序后的快速查找。 【问题描述】 为加快速度需先数据记录按关键字排序,在汽车数据模型中,汽车是关键字,而且是具有结构特点的一类关键字。因为汽车牌照是汉字...
  • [NOIP算法]快速排序——双关键字

    千次阅读 2013-01-11 21:15:01
    关于快排的双关键字排序。 要求:a[i]按照从小到大排序,a[i]相同则按b[i]从小到大排序。 核心:先比较a[i],按正常排序;或则a[i]相同,则b[i]按照顺序也可通过。 代码: program qsort_double; var n,i:long...
  • 按照主关键字和次关键字排序

    千次阅读 2014-04-05 14:11:43
    #include #include ...void quick_sort(int *s,int *f,int low,int high)//快速排序,安装活动的开始时间升序排序 { while (low){ int pivot=s[high]; int k=low-1; int tmp; for(int i=low;i;+
  • 快速排序算法——C/C++

    万次阅读 多人点赞 2019-06-12 22:55:14
    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别这两部分记录继续进行排序,以达到整个序列有序。 2、实现原理 2.1、设置两变量 low、...
  • 快速排序的平均时间复杂度是N*logN,同时其也是实践已知的最快的通用排序算法,但是其最坏情况的时间复杂度依然是N的平方,但是只要我们对快速排序算法稍作修改,就可以保证其最坏情况的时间复杂度也是N*logN。...
  • 快速排序

    2016-04-21 10:45:04
    快速排序的基本思想是:选出一个关键字,通过一次遍历,把比关键字小的数据都放到关键字左边,把比关键字大的数据都放到关键字的右边。然后在左右两边依次进行快速排序快速排序的时间复杂度: 最坏的情况:所选...
  • 快速排序时间复杂度分析

    千次阅读 2020-09-21 20:57:09
    快速排序的时间主要耗费在划分操作上,长度为n的区间进行划分,共需n-1次关键字的比较,时间复杂度为O(n)。 对n个元素进行快速排序的过程构成一棵递归树,在这样的递归树中,每一层最多对n个元素进行划分,所花...
  • 完全不同于以前的排序算法,可以说,基数排序也叫做多关键字排序,基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 两种方式: 1、最高位优先,先按照最高位排成若干子序列,再...
  • 一、算法简介快速排序的基本步骤是: 每一次排序时选择一个关键字,一趟排序后待排序的数据被分割成两部分,其中一部分的数据均比该关键字大,另一部分的关键字均比该关键字小; 分别两部分的数据继续进行排序...
  • 1.元素的移动次数与关键字的初始排列次序无关的是:基数排序。2.元素的比较次数与初始序列无关是:选择排序。3.算法的时间复杂度与初始序列无关的是:直接选择排序。4.选择排序一定是n-1趟排序,比较的次数永远是n(n...
  • 常用内部排序算法之二:快速排序

    千次阅读 2015-12-01 20:51:11
    快速排序算法的思想是:通过一趟快速排序将待排序的记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的记录的关键字小,则可分别这两部分记录继续进行排序,达到整个记录有序。实现快速排序算法的核心...
  • C语言快速排序

    千次阅读 多人点赞 2018-12-25 19:46:10
    快速排序(Quick Sort)概念:是由冒泡排序改进而得到的。在冒泡排序过程中,只相邻的...快速排序的算法步骤:在待排序的n个记录中任取一记录(通常取第一记录)作为枢轴(或支点),设其关键字为pivotkey。经...
  • 快速排序深度优化详解

    万次阅读 2019-02-24 17:25:36
    正如它的名字所体现,快速排序是在实践中最快的已知排序算法,平均运行时间为O(NlogN),最坏的运行时间为O(N^2)。算法的基本思想很简单,然而想要写出一高效的快速排序算法并不是那么简单。基准的选择,元素的分割...
  • 快速排序(三种算法实现和非递归实现)

    万次阅读 多人点赞 2017-11-29 18:41:44
    快速排序(Quick Sort)是冒泡排序的一种改进,基本思想是选取一记录作为枢轴,经过一趟排序,将整段序列分为两部分,其中一部分的值都小于枢轴,另一部分都大于枢轴。然后继续这两部分继续进行排序,从而使...
  • 对n个记录的线性表进行快速排序为减少算法的递归(栈)深度,每次分区后,先处理较短的部分。 举栗子。 现在有这么序列:123456789 假设每次划分出短序列的长度为1 即第一次划分 短序列:1 长序列:23456789 如果...
  • 快速排序(Quick Sort)

    千次阅读 多人点赞 2019-09-27 16:45:14
    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别这两部分记录继续进行排序,以达到整个序列有序。 算法描述 快速排序使用分治法来把一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 77,577
精华内容 31,030
关键字:

对n个关键字做快速排序