精华内容
下载资源
问答
  • 顺序表实现堆排序和快速排序,输入的元素个数不限可以直接确定,C语言
  • 快速排序 C语言实现

    2020-11-19 22:06:22
    快速排序 快速排序(Quick Sort )是由冒泡排序改进而得的。在冒泡排序过程中,只对相邻的两个记录进行比较,因此每次交换两个相邻记录时只能消除一个逆序。 如果能通过两个(不相邻)记录的一次交换,消除多个逆序,则...

    快速排序

    快速排序(Quick Sort )是由冒泡排序改进而得的。在冒泡排序过程中,只对相邻的两个记录进行比较,因此每次交换两个相邻记录时只能消除一个逆序。 如果能通过两个(不相邻)记录的一次交换,消除多个逆序,则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。

    课本上的例子:

    在这里插入图片描述
    时间复杂度

    最好情况:O(n l o g 2 log_2 log2n)
    最坏情况:O( n 2 n^2 n2)
    平均情况:O(n l o g 2 log_2 log2n)

    空间复杂度

    O( l o g 2 log_2 log2n)

    算法特点:

    1)记录非顺次的移动导致排序方法是不稳定的。
    2)排序过程中需要定位表的下界和上界,所有适合用于顺序结构,很难用于链式。
    3)当n较大时,在平均情况下快速排序是所有内部排序方法中速度最快的一种,所以其适合初始记录无序、n较大时的情况。

    完整代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 100  //顺序表最大容量,可以自行加大 
    
    typedef struct 
    {
    	int key;//关键字项 
    	char *otherinfo;//其他数据项 
    }ElemType;//记录类型 
    typedef struct
    {
    	ElemType Data[MAXSIZE+1];//静态顺序表的数据域,这里Data[0]为空闲或者为哨兵单元 
    	int length;//顺序表的长度 
    }SqList;//顺序表 
    
    void InitList(SqList &L)//顺序表的初始化 
    {
    	L.length = 0;//使顺序表长度归0,便是顺序表的初始化 
    }
    
    void CreateList(SqList &L)//顺序表的创建 
    {
    	printf("请输入:"); 
    	while(1)//建立一个死循环,循环终止条件是按了enter键 
    	{
    		L.length++;//顺序表长度加一 
    		if(L.length>MAXSIZE)//判断是否超出最大容纳量 
    		{
    			printf("顺序表已满!\n");
    			return ;
    		}
    		scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
    		if(getchar() == '\n')//循环终止条件 
    			break;
    	}
    }
    
    void InputList(SqList L)//顺序表的输出 
    {
    	int i;//记录次数 
    	if(L.length == 0)//判断顺序表是否为空 ,若为空结束该函数 
    	{
    		printf("顺序表是空的!\n");
    		return ;
    	}
    	printf("打印为:");
    	for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
    		printf("%d ",L.Data[i].key);	
    }
    
    int Partition(SqList &L,int low,int high)//对顺序表L中的子表Data[low…high]进行一趟排序,返回驱轴位置 
    {
    	L.Data[0] = L.Data[low];//用子表的第一个记录做驱轴记录  
    	while(low < high)//当low==high时终止循环 ,从表的两端交替地向中间扫描 
    	{
    		while(low<high&&L.Data[0].key<=L.Data[high].key)
    			high--;
    		L.Data[low] = L.Data[high];//将比驱轴记录小的记录移到低端 
    		while(low<high&&L.Data[0].key>=L.Data[low].key)
    			low++;
    		L.Data[high] = L.Data[low];//将比驱轴记录大的记录移到高端 
    	}
    	L.Data[low] = L.Data[0];//驱轴记录到位 
    	return low;//返回驱轴位置 
    }
    int pivotloc;//递归函数中不宜定义变量,故定义一个全局变量 
    void QSort(SqList &L,int low,int high)//调用前置初值:low=1;high=L.length; 
    {//对顺序表L中的字序列L.Data[low…high]做快速排序,递归算法 
    	if(low < high)//长度大于1,递归终止条件 
    	{
    		pivotloc = Partition(L,low,high);//将L.Data[low…high]一分为二,pivotloc是驱轴位置 
    		QSort(L,low,pivotloc-1);//对左子表递归排序 
    		QSort(L,pivotloc+1,high);//对右子表递归排序 
    	}
    }
    void QuickSort(SqList &L)//对顺序表L做快速排序 
    {
    	QSort(L,1,L.length);
    }
    
    int main()
    {
    	SqList L;
    	InitList(L);//初始化顺序表 
    	CreateList(L);//创建顺序表 
    	QuickSort(L);//快速排序 
    	InputList(L);//打印排序后结果 
    	return 0;
    }
    
    

    在这里插入图片描述
    (完)

    展开全文
  • 快速排序是20世纪的十大算法之一,在常见的o(nlogn)的时间复杂度的算法(快速排序,堆排序,2路归并排序)中,快速排序的平均性能也是最优的,下面是快排的c语言实现代码 // 基本思想是分治法,故一般用到递归 ...

    快速排序是20世纪的十大算法之一,在常见的o(nlogn)的时间复杂度的算法(快速排序,堆排序,2路归并排序)中,快速排序的平均性能也是最优的,下面是快排的c语言实现代码

    // 基本思想是分治法,故一般用到递归
    void QuickSort(int L[],int low, int high) //low和high指示排序的范围
    {
         int temp=0; //用于存储待交换的元素的值
         int i=low,j=high;
         if(low<high)
         {
            temp=L[low]//序列中第一个关键字作为枢轴元素
            while(i<j)
            {
               while(i<j&&temp<=L[j])  //从右往左扫描
               --j;
               if(i<j)
               {
                  L[i]=L[j]
                  ++i;     
               }
                 while(i<j&&temp>=L[i])  //从左往右扫描
               ++i;
               if(i<j)
               {
                  L[j]=L[i]
                  --j;     
               }
            }     
         }//一次排序完成  
          L[i]=temp;//此时temp已经被放在最终位置上,左边的元素均比其小,右边的元素均比其大
         QuickSort(int L[],int low, i-1);
         QuickSort(int L[],int i+1, high); //递归,对分成的两个子序列进行快速排序
         
    }
    
    展开全文
  • 快速排序c语言程序

    2018-05-29 17:32:20
    #define MAXSIZE 20//顺序表的最大长度#define LT(a,b) ((a)&lt;(b))typedef int KeyType;//定义关键字的类型为整型typedef char InfoType;//定义其他信息为字符类型typedef struct{ KeyType key;//关键字项 ...
    #include<stdio.h>
    
    #define MAXSIZE 20//顺序表的最大长度
    #define LT(a,b) ((a)<(b))
    typedef int KeyType;//定义关键字的类型为整型
    typedef char InfoType;//定义其他信息为字符类型


    typedef struct
    {
        KeyType key;//关键字项
        InfoType otherinfo;//其他数据项
    }RedType;


    typedef struct
    {
        RedType r[MAXSIZE+1];//r[0]闲置或作为监视哨
        int length;//顺序表长度
    }SqList;


    int ptime=0;//划分序列的次数
    void print(SqList &L)
    {
        int i;
        for(i=1;i<=L.length;i++)
           printf("%-3d",L.r[i].key);
        printf("\n");
    }
    //对L.r[low...high]做划分,使枢轴记录到位,并返回其位置
    int Partition(SqList &L,int low,int high)
    {
        int pivotkey;
        L.r[0]=L.r[low];
        pivotkey=L.r[low].key;
        while(low<high)
        {
            while(low<high&&L.r[high].key>=pivotkey)
            --high;
            L.r[low]=L.r[high];
            while(low<high&&L.r[low].key<=pivotkey)
            ++low;
            L.r[high]=L.r[low];
        }
        L.r[low]=L.r[0];
        ptime++;
        printf("第%d次划分排序为:",ptime);
        print(L);
        return low;
    }
    //递归法对L中的序列做快速排列
    void Qsort(SqList &L,int low,int high)
    {
        int pivotloc;
        if(low<high)
        {
            pivotloc=Partition(L,low,high);
            Qsort(L,low,pivotloc-1);
            Qsort(L,pivotloc+1,high);
        }
    }


     int main()
     {
         int i;
         SqList L;
         printf("输入要排序的列表长度n:");
         scanf("%d",&L.length);
         for(i=1;i<=L.length;++i)
         {
             printf("输入第%d个记录的关键字;",i);
             scanf("%d",&L.r[i].key);
         }
         printf("初始关键字为:");
         print(L);
         Qsort(L,1,L.length);
         printf("快速排序后的记录为:");
         print(L);
     }
    展开全文
  • 顺序表快速排序

    千次阅读 2018-07-31 23:02:17
    c语言建立顺序表,实现快速排序。 这里是用了两个函数实现的,一个分割函数,一个递归。 #include&lt;stdio.h&gt; #define ListSize 20 typedef int DataType; typedef struct{ DataType data[List...

    用c语言建立顺序表,实现快速排序。

    这里是用了两个函数实现的,一个分割函数,一个递归。

    #include<stdio.h>
    #define ListSize 20
    typedef int DataType;
    typedef struct{
    	DataType data[ListSize];
    	int length;
    }Seqlist;
    
    Seqlist CreateList(Seqlist L)  //结构体变量作为函数的参数,修改之后的成员值不能返回到主调函数,不过可以return返回它
    {
        int n;
        L.length=0;
        printf("输入顺序表的数据:输入-1结束\n");
    	while(1)
        {
            scanf("%d",&n);
            if(n==-1) break;
            L.data[L.length]=n;
            L.length++;
        }
        return L;
    }
    
    void DisplayList(Seqlist *L)
    {
        int i;
        for(i=0;i<L->length;i++)
        {
            printf("%d,",L->data[i]);
        }
        printf("\n");
    }
    
    int Patition(Seqlist *L,int low,int high)  //把顺序表一分为二,并且返回枢轴位置
    {
        DataType pivotvalue=L->data[low];    //用第一个数作为枢轴,pivotvalue保存枢轴的值
        while(low<high)   //当low==high时两边相遇了,结束一趟排序
        {
            while(low<high&&L->data[high]>=pivotvalue)  //先从右往左找比pivotvalue小的数, 
                                                        //注意等号
                high--;
            L->data[low]=L->data[high];             //找到后放到前边
    
            while(low<high&&L->data[low]<=pivotvalue)  //从前往后找比pivotvalue大的数
                low++;
            L->data[high]=L->data[low];   //放到后边
    
        }
        L->data[low]=pivotvalue; //枢轴此时放到low和high相遇的地方
        return low;  //返回枢轴位置
    
    }
    void ListQSort(Seqlist *L,int low,int high)  //快排
    {
    
        if(low<high)
        {
            int pivotlocation = Patition(L, low, high);
            ListQSort(L,low,pivotlocation-1);
            ListQSort(L,pivotlocation+1,high);
        }
    
    }
    
    int main()
    {
        int i,n;
        Seqlist mylist;
        mylist=CreateList(mylist);
    
    	DisplayList(&mylist);
    	printf("长度:%d\n",mylist.length);
    	ListQSort(&mylist,0,mylist.length-1);
    	DisplayList(&mylist);
    }
    

    接着用一个函数来实现吧,原理是一样的,但是要注意low和high的初始值得保留。

    void QuickSort(Seqlist *L,int low,int high)
    {
        int i=low,j=high;  //low和high的位置待会递归的时候要用到,所以不能和上边一样直接修改
        DataType pivotvalue=L->data[i];  //注意这里要用data[i]
        if(low>=high)  //一趟排序结束
            return;   
        while(i<j)
        {
            while(i<j&&L->data[j]>=pivotvalue)
                j--;
            L->data[i]=L->data[j];
            while(i<j&&L->data[i]<=pivotvalue)
                i++;
            L->data[j]=L->data[i];
        }
        L->data[i]=pivotvalue;
        QuickSort(L,low,i-1);
        QuickSort(L,i+1,high);
    }

     

    展开全文
  • 顺序表定义的长度为10000,此时程序可以正常运行;把顺序表长度改成500000,程序出错,不能运行。求问大神是哪里出了错误,还是要提高存储上限?如何改正?#include #include #include typedef int ElemType; #...
  • 快速排序C语言实现

    2017-08-10 23:17:01
    快速排序主要过程如下: 分解:数组A[p..r]被划分为两个(可能为空的)子数列A[p..q-1]和A[q+1..r],使得A[p..q-1]中元素都小于等于A[q],A[q+1..r]中元素都大于A[q]。 解决:通过递归调用快速排序,对子数组A[p.....
  • 快速排序(C语言简单实现) 快速排序(Quick Sort)是冒泡排序的升级版。基本思想:通过一趟排序将待排记录分割成独立的两部分.../* 对顺序表L作快速排序 */ void QuickSort(SqList *L){ QSort(L, 1, L->length); }
  • 冒泡排序和快速排序C语言实现) 冒泡排序 冒泡排序的原理是:从左到右,相邻元素进行比较。每次比较一轮,就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。 以从大到小排序为例,第一轮...
  • 本文较为详细地整理了快速排序的大体思路;并用c语言进行了实现。
  • 快速排序c语言实现)

    万次阅读 多人点赞 2018-04-05 15:00:47
    #define MAXSIZE 10 //要排序数组个数的最大值 typedef struct { int r[MAXSIZE + 1]; //存储要排序数组,r[0]用作哨兵或临时变量 int length; }SqList; void swap(SqList *L, int i, in...
  • 顺序表的结构 void Creatlist ( SStable * LIST ) // 创建线性表,注意此处的 LIST 是指针类型,为了使返回这个线性表 { int i ; printf ( "Please input how many the number is: \n " ) ; scanf...
  • 八种基本的排序(1)——冒泡排序(C语言实现)八种基本的排序(2)——直接选择排序(C语言实现)八种基本的排序(3)——插入排序(C语言实现)八种基本的排序(4)——归并排序(C语言实现)八种基本的排序(5)——快速排序(C语言...
  • 之前五一放假之前写过一篇博客(基于c语言实现的顺序表),这篇博客将会在上一篇的基础上继续实现各种排序 当然下面也会简单介绍一下上一篇的主要函数,不看上一篇也能理解这一篇的各种排序 下面附上上一篇的链接...
  • //严蔚敏数据结构快速排序算法c语言实现#includetypedef int InfoType; /* 定义其它数据项的类型 *//* c10-1.h 待排记录的数据类型 */#define MAXSIZE 20 /* 一个用作示例的小顺序表的最大长度 */typedef int Key...
  • 首先定义顺序表,实现由小到大的排序 typedef int ElemType ; typedef struct { ElemType *elem; int length; int listsize; }SqList;//SqList是结构体名字 L.length为数组长度 冒泡排序法:将每...
  • C语言快速排序 ** #include <stdio.h> #include<string.h> void quick_sort(int *a,int n) { int i,j,p,temp; if(n<2)return; p=a[n/2];//获取数组基准值 for(i=0,j=n-1;;i++,j--) { while(a...
  • 八种基本的排序(5)——快速排序C语言实现)

    万次阅读 多人点赞 2018-07-29 17:43:35
    快速排序(quick-Sort) 算法介绍 排序演示 示例 调用函数 快速排序(quick-Sort) 是对冒泡排序的一种改进。1 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的...
  • 线性表采用顺序存储的方式存储就称之为顺序表顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 线性表的动态分配顺序结构: typedef struct{//顺序表的存储结构定义 DataType data[L.
  • C语言快速排序

    千次阅读 2013-10-12 09:51:04
    虽然算法在最坏的情况下运行时间为O(n^2),但由于平均运行时间为O(nlogn),并且在内存使用、程序实现复杂性上表现优秀,尤其是对快速排序算法进行随机化的可能,使得快速排序在一般情况下是最实用的排序方法之一。...
  • 顺序表的实现--C语言泛型编程

    千次阅读 2016-08-21 20:48:20
    一:顺序表代码实现 #ifndef _SEQ_LIST_H #define _SEQ_LIST_H #include #include #include #include #define ElemType float //以float类型测试算法通用性,而不是以惯用的int #define INIT_SIZE 10 //顺序表...
  • //严蔚敏数据结构快速排序算法c语言实现 #include typedef int InfoType; /* 定义其它数据项的类型 */ /* c10-1.h 待排记录的数据类型 */ #define MAXSIZE 20 /* 一个用作示例的小顺序表的最大长度 */ typedef int ...
  • 快速排序的原理 快速排序(Quicksort)是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分...
  • 作者:李慧芹,华清远见嵌入式学院讲师。快速排序实质上是对“冒泡排序”的一种改进,整个排序过程可概括为:通过N趟的排序将原本的排序数据分为若干...假设我们现对一列数进行快速排序,其C语言代码实现如下:#include
  • 主要介绍了C++中实现选择排序、冒泡排序和快速排序的代码示例,例子带有执行时间统计还可以简单看一下效率对比,需要的朋友可以参考下
  • 排序 C语言实现

    2020-11-20 16:42:37
    (Heap Sort) 是一种树形选择排序,在排序过程中,将待排序的记录Data[1…n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩 子结点之间的内在关系,在当前无序的序列中选择关键字最大(或最小)的...
  • 快速排序是由冒泡排序改进而得的,相比冒泡排序,快速排序的一次交换可能消除多个逆序。其平均时间复杂度为O(nlog2n),空间复杂度最好情况下为O(log2n),最坏情况下为O(n)。适用于顺序结构,不适用于链式结构,不稳定...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,505
精华内容 7,402
关键字:

顺序表快速排序c语言

c语言 订阅