首页 > 代码库 > 数据结构之快速排序

数据结构之快速排序

2024-07-15 04:47:54   221人阅读

 

1.快速排序思想

     快速排序基本思想是：通过一趟排序将序列分成独立的两部分，其中一部分的关键字都小于或都大于另一部分的关键字，则可以对这两部分记录继续排序，达到整个序列有序位置。假设待排序记录a1,a2...an,n个记录，首先任意选取一个记录作为轴pivot，将比它小的记录放到其左边，将比它大的记录放到其右边，这成为一趟排序。然后将左右两部分通过上述规则递归排序。

 

2.快速排序代码实现

  1 #include <stdio.h>  2 #include <stdlib.h>  3 #include <time.h>  4 #define MAXSIZE 100000000  5 #define INCREMENTNUM 200000  6 #define EQ(a,b) ((a)==(b))  7 typedef struct List{  8     int*elem;  9     int length; 10     int size; 11 }List; 12  13 void initList(List &list) 14 { 15     list.elem=(int*)malloc(sizeof(int)*(MAXSIZE+1)); 16     if(!list.elem){ 17          printf("%s\n","初始化失败"); 18         exit(0); 19     } 20     list.length=0; 21     list.size=MAXSIZE; 22     printf("%s\n","初始化成功"); 23 } 24  25 void insert(List &list ,int value) 26 { 27     if(list.length>=list.size){ 28         list.elem=(int*)realloc(list.elem,sizeof(int)*(list.length+INCREMENTNUM)); 29         if(!list.elem){ 30          printf("%s\n","内存重新分配失败"); 31         exit(0); 32         } 33         printf("%s\n","内存重新分配成功"); 34     list.size+=INCREMENTNUM; 35     } 36     list.elem[++list.length]=value; //第一从1开始 37     //printf("%d%s  位置：%d\n",value,"\t插入成功",list.length); 38 } 39  40 int search(List list,int key) 41 { 42     list.elem[0]=key; 43     int i; 44     long start=clock(); 45     for(i=list.length;!EQ(list.elem[i],key);i--); 46     long end=clock(); 47     printf("耗时：%lf  秒\t%s\n",(double)(end-start)/1000,"查找完成"); 48     return i; 49 } 50  51 void printList(List list) 52 { 53     //printf("共%d数据\n",list.length); 54     int i; 55     for(i=1;i<=list.length;i++){ 56         printf("%d\t",list.elem[i]); 57     } 58     printf("\n"); 59  60 } 61  62 int Partition(List &L,int low,int high) 63 { 64     L.elem[0]=L.elem[low]; 65     int pivokkey=L.elem[low]; 66     while(low<high){ 67         while(low<high&&L.elem[high]>=pivokkey) --high; 68         L.elem[low]=L.elem[high]; 69         while(low<high&&L.elem[low]<=pivokkey) ++low; 70         L.elem[high]=L.elem[low]; 71     } 72     L.elem[low]=L.elem[0]; 73     return low; 74 } 75 void QSort(List &L,int low,int high) 76 { 77     if(high>low) 78     { 79         int pivok=Partition(L,low,high); 80         QSort(L,low,pivok-1); 81         QSort(L,pivok+1,high); 82     } 83 } 84 void QuickSort(List &L) 85 { 86     QSort(L,1,L.length); 87 } 88 int main() 89 { 90  91     List list; 92     initList(list); 93     insert(list,49);insert(list,38);insert(list,65);insert(list,97);insert(list,76); 94     insert(list,13);insert(list,27);insert(list,49); 95     printList(list); 96     QuickSort(list); 97     printf("排序后\n"); 98     printList(list); 99     return 0;100 }

3.显示结果

4.快速排序性能

     快速排序QuickSort，就平均时间而言，目前被认为是最好的一种内部排序方法。在所有同数量级O(nlogn）的排序算法中，其平均性能最好，但是初始序列按关键字有序或者基本有序时，快速排序将蜕变为冒泡法，其时间复杂度O(n^2)。


联系
我们