首页 > 代码库 > 快速排序、堆排序和归并排序的实现

快速排序、堆排序和归并排序的实现

2024-07-04 07:32:57   222人阅读

　　　　1、快速排序

　　　　通过选择轴值，一次划分都能确定该轴值得位置，其时间复杂度最好的情况（每次划分都恰好将区间平分为等长的两半）下为Ο（nlgn），最差情况（每次划分将区间分成0与n-1）为O(n^2)。其空间复杂度考虑递归的栈深为O(lgn)。

 1 /*************************************************************************
 2 **File Name            :quicksort.c
 3 **Author            :
 4 **Contact            :
 5 **Created Time        :Mon 12 May 2014 02:12:57 PM CST
 6 **Brief                :
 7 **Development note    :
 8  ************************************************************************/
 9 
10 /********************************include*********************************/
11 #include<stdio.h>
12 
13 int partition(int a[],int start,int end)
14 {
15     int i,j,tmp;
16     i = start;
17     j = end;
18     while(i < j){
19         while(a[i] < a[j] && i < j){
20             j--;
21         }
22         if(i < j){
23             tmp = a[i];
24             a[i] = a[j];
25             a[j] = tmp;
26             i++;
27         }
28         while(a[i] < a[j] && i < j){
29             i++;
30         }
31         if(i < j){
32             tmp = a[i];
33             a[i] = a[j];
34             a[j] = tmp;
35             j--;
36         }
37     }
38     return i;
39 }
40 int quicksort(int a[],int start,int end)
41 {
42     if(start >= end)
43         return 0;
44     int mid;
45     mid = partition(a,start,end);
46     quicksort(a,start,mid-1);
47     quicksort(a,mid+1,end);
48 }

　　　　2、堆排序

　　　　堆排序通过堆顶的对换和堆的不断调整实现。其时间复杂度为O(nlgn)，与初始序列无关。

 1 /*************************************************************************
 2 **File Name            :heapsort.c
 3 **Author            :
 4 **Contact            :shixuyong@scit.ac.cn
 5 **Created Time        :Mon 12 May 2014 02:40:23 PM CST
 6 **Brief                :
 7 **Development note    :
 8  ************************************************************************/
 9 /*
10 *澶ф牴鍫*鏁扮粍浠寮€濮*/
11 /********************************include*********************************/
12 #include<stdio.h>
13 void sift(int a[],int k,int m)
14 {
15     int i = 2*k,tmp;
16     /*
17     * 璋冩暣浜唅 = 2*i鐨勪綅缃紝鏀惧埌寰幆鐨勬渶鍚庛€傚惁鍒欏嚭閿欍€    * */
18     while(i <= m){
19         if(a[i] < a[i+1]&& i+1 <= m)
20             i = i+1;
21         if(a[i] > a[k]){
22             a[0] = a[i];
23             a[i] = a[k];
24             a[k] = a[0];
25             k = i;
26             i = 2*i;
27         }
28         else
29             break;
30     }
31 }
32 void heapsort(int a[],int m)
33 {
34     int i,tmp,j=0;
35     for(i = m/2; i > 0; i--){
36         sift(a,i,m);
37     }
38     for(i = 1;i < m; i++){
39         a[0] = a[1];
40         a[1] = a[m-i+1];
41         a[m-i+1] = a[0];
42         sift(a,1,m-i);
43     }
44 }

　　　　3、归并排序

　　　　归并的思想在于，每次合并两个相邻的一排序的序列，多次归并实现排序。其时间复杂度为O(nlgn)与初始序列无关，空间复杂度为O(n) 。

 

 1 /*************************************************************************
 2 **File Name            :mergesort.c
 3 **Author            :Shi Xuyong
 4 **Contact            :shixuyong@scit.ac.cn
 5 **Created Time        :Mon 12 May 2014 08:23:27 PM CST
 6 **Brief                :
 7 **Development note    :
 8  ************************************************************************/
 9 
10 /********************************include*********************************/
11 #include<stdio.h>
12 /*
13 */
14 void merge(int a[],int b[],int s,int m,int t)
15 {
16     int i,j,k;
17     i = s;
18     j = m+1;
19     k = i;
20     while(i <= m && j <= t){
21         if(a[i] < a[j]){
22             b[k++] = a[i++];
23         }
24         else{
25             b[k++] = a[j++];
26         }
27     }
28     if(j <= t){
29         while(j <= t ){
30             b[k++] = a[j++];
31         }
32     }
33     else{
34         while(i <= m){
35             b[k++] = a[i++];
36         }
37     }
38 }
39 void mergepass(int a[],int b[],int n,int h)
40 {
41     int i = 1;
42     while(i <= n-2*h+1){
43         merge(a,b,i,i+h-1,i+2*h-1);
44         i = i+2*h;
45     }
46     if(i < n-h+1)
47         merge(a,b,i,i+h-1,n);
48     else{
49         int k;
50         for(k = i; k<=n; k++)
51             b[k] = a[k];
52     }
53 }
54 void mergesort(int a[],int b[],int n)
55 {
56     int h = 1;
57     while(h < n){
58         mergepass(a,b,n,h);
59         h = h*2;
60         mergepass(b,a,n,h);
61         h = h*2;
62     }
63 }

 

 

 

上述三种算法只有归并排序是稳定的，其余两个都不稳定。

堆排序用在筛选数组中最大（小）的K个数，快速排序用在查找数组的第K大（小）数。归并排序性能相对较好。


联系
我们