排序算法

本文最后更新于 2024年9月10日 下午

排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
 
int count;//排序趟数

//一些排序需要用到交换 
void swap(int* a, int* b) {
    int temp = *b;
    *b = *a;
    *a = temp;
} 

//堆排序，adjust是调整函数 
void adjust(int k[ ],int i,int n)
{
    int j,parent;
    parent=k[i];//注意parent一直没变 
    j=2*i+1;//j是左孩子 
    while(j<=n){
     count++;
        if(j<n&&k[j]<k[j+1])
            j++; //j给出i结点左、右孩子中最大值的节点 
        if(parent>=k[j]) 
            break; //如果孩子节点最大值小于根节点，不用交换 
        k[(j-1)/2]=k[j]; //把最大的孩子节点移到父节点位置 
        
        j=2*j+1;//防止交换以后使得子树不是大顶堆，把j看作子树的父节点 
    }//循环结束时 
    k[(j-1)/2]=parent;//把父亲节点parent放到最后 
}

void heapsort(int k[],int n){
 int i;
 int temp;
 for(i=n/2;i>=0;i--)
 adjust(k,i,n);//先从最后一个节点的父节点开始调整，一个个往前推 
 
 for(i=n-1;i>0;i--){
  temp=k[i+1]; 
  k[i+1]=k[0];
  k[0]=temp;//此时根节点破坏了整个树的堆的特性，把根节点放到最后一个节点 
  adjust(k,0,i-1);//再对新得到的树进行堆调整 
 }
}

//堆排序的另一个版本，更加容易理解 

void max_heapify(int arr[], int i, int n ) {
    //建立父节点指标和子节点指标
      int largest = i; // 将最大元素设置为堆顶元素
      int l = 2 * i + 1; // left = 2*i + 1
      int r = 2 * i + 2; // right = 2*i + 2
  
      // 如果 left 比 root 大的话
      if (l <=n && arr[l] > arr[largest])
          largest = l;
  
      // I如果 right 比 root 大的话
      if (r <=n && arr[r] > arr[largest])
          largest = r;
  
      if (largest != i) {
          swap(&arr[i],&arr[largest]);
          // 递归地定义子堆
          max_heapify(arr, n, largest);
      }
 
}

void heap_sort(int arr[], int len) {
    int i;
    //初始化，i从最后一个父节点开始调整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
        
    //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}


//二路归并排序 
void MergeArray(int a[],int head,int mid,int tail)
{
 //p即为左半部分数组和右半部分数组排序合并后的数组 
 int i=head,j=mid+1,k=0;
 int *p=(int *)malloc(sizeof(int)*(tail-head+1));
 while(i<=mid&&j<=tail)
 {
  count++;
  if(a[i]<=a[j])p[k++]=a[i++];
  else p[k++]=a[j++]; 
  
 }//对左半数组和右半数组进行比较，从小到大排序构建p 
 while(i<=mid)p[k++]=a[i++];//把左半部分没合并的加入到p中 
 while(j<=tail)p[k++]=a[j++];//把右半部分没合并的加入到p中 
 for(k=0;k<=tail-head;k++)a[head+k]=p[k];//把p放到a的对应位置中 
 free(p);
 
}

void MergeSort(int a[],int head,int tail)
{
 if(head<tail)
 {
  int mid=(head+tail)/2;
  MergeSort(a,head,mid);//对左半部分进行排序 
  MergeSort(a,mid+1,tail);//对右半部分进行排序 
  MergeArray(a,head,mid,tail);//对左右两边的数组进行合并 
 }
}


//快排 
void quickSort(int k[ ],int left,int right)
{     
    int i, last;
    if(left<right){
       last=left; 
        for(i=left+1;i<=right;i++){
         count++;
            if(k[i]<k[left]&&(++last)<i)
         swap(&k[last],&k[i]);
 //不断把k[i]中小于k[left]的元素往左移动，使得last正好指在小于left元素的最右边，last右侧的元素均大于left 
  }
        swap(&k[left],&k[last]);//交换last和left处的元素 
        quickSort(k,left,last-1); 
        quickSort(k,last+1,right);   
    }
}

//统计排序趟数 
int main(){
    int n,op;
    int a[120];
    scanf("%d%d",&n,&op);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    switch (op) {
    case 1:
    selectsort(a,n);
        break;
    case 2:
    bubblesort(a,n);
        break;
    case 3:
    heapsort(a,n-1);
        break;
    case 4:
    MergeSort(a,0,n-1);  
        break;
    case 5:
    quickSort(a,0,n-1);       
        break;
    }
    for(int i=0;i<n;i++)
    printf("%d ",a[i]);
    printf("\n%d",count);
    return 0;
}