Mrli
别装作很努力,
因为结局不会陪你演戏。
Contacts:
QQ博客园

数据结构实验4——各种内排序算法的实现及性能比较

2021/02/20 C 数据结构
Word count: 3,083 | Reading time: 16min

部分代码

辅助函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**生成随机数**/
void RandCreate(int *a){
    int i;
    for ( i = 0; i < N; ++i)
        a[i] = 1 + (rand()%1000);
}

/***交换数组中,两个下标的值***/
void Swap(int *a,int i,int j){
    int tmp;
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

简单选择排序

1
2
3
4
5
6
7
8
9
/**简单选择排序**/
void SelectSort(int *l){
    int minx,i,j;
    for (i= 0; i < N-1; ++i){
        minx = i;   //默认标记为每次第一位元素下标
        for (j = i+1; j < N; ++j) if( l[minx] > l[j] ) minx = j;
        if( minx != i) Swap(l,minx,i); //判断起始位置是否为最小值
    }
}

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
/**直接插入排序**/
void InsertSort(int *l){
    int i,j;                                 //i标识待插入元素下标
    for(i = 1;i < N;i ++){
        int insertItem = l[i];              //标记每次第一位元素
        for(j = i-1;j >= 0;j --){
            //不断将有序序列中元素向后移动,为待插入元素空出一个位置
            if(insertItem < l[j]) l[j+1] = l[j];
            else break;
        }
        l[j+1] = insertItem;          //待插入元素有序存放至有序序列中
    }
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//冒泡排序
void BubbleSort(int *l){
    int i,j;
    //i标识每趟排序范围最后一个元素下标,每趟排序元素下标范围是0~i
    for(i = N-1;i > 0;i --){
        int isSwap = 0;         //教材错误,应该放到第二层循环前
        for(j = 0; j<i;j ++){
            if(l[j] > l[j+1]){
                Swap(l,j,j+1);
                isSwap = 1;
            }
        }
        if(!isSwap) break;
        //如果本趟排序没有发生元素交换,则直接可以认为排序已完成
    }
}

快速排序

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
#include<iostream>
using namespace std;
void quickSort(int a[], int m,int n);
int partion(int a[], int m, int n);
int main()
{
	int a[] = { 6,1,2,7,9,3,3,4,5,10,8 };
	int m = 0;
	int n = (sizeof(a) / 4)-1;
	quickSort(a, m,n);
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";
	}
}
void quickSort(int a[], int m, int n)
{
	if (m < n)
	{
		int q = partion(a, m, n);
		quickSort(a, m, q-1);
		quickSort(a, q + 1, n);
	}
}
int partion(int a[], int m, int n)
{
	int key=m;			// m为左, n为右边界
	int j= n,i=m;		
	int temp1, temp2;
	while (i != j)
	{
		while (a[j] >= a[key] && i < j)
		{
			--j;
		}
		
		while ((a[i] <= a[key]) && (i < j))
		{
			++i;
		}
        if (i < j)
		{
			temp1 = a[j];
			a[j] = a[i];
			a[i] = temp1;
		}
	}
		temp2 = a[key];
		a[key] = a[i];
		a[i] = temp2;
		return i;
}

两路合并排序

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
//Merge函数,参考了陈慧南老师的《数据结构——C语言描述》教材
void Merge(int *l,int Temp[],int i1,int j1,int i2,int j2,int *k){
    int i = i1,j = i2;
    while((i <= j1)&&(j<=j2)){                       //若两个子序列都不空,则循环
        if(l[i] <= l[j]){
            Temp[(*k)++] = l[i++];         //将较小元素存入Temp[*k]
        }
        else Temp[(*k)++] = l[j++];
    }
    while(i <= j1) Temp[(*k)++] = l[i++];  //将子序列1中剩余元素存入Temp
    while(j <= j2) Temp[(*k)++] = l[j++];  //将子序列2中剩余元素存入Temp
}


//MergeSort函数
void MergeSort(int *l){
    int Temp[N];
    int i1,j1,i2,j2,i,k,size = 1;              
    //i1,j1和i2,j2分别是两个子序列的上,下界
    while(size < N){
        i1 = 0;
        k = 0;
        while(i1+size < N){              
            //若i1+size < n,则说明存在两个子序列,需要再两两合并
            i2 = i1+size;                      //确定子序列2的下界和子序列1的上界
            j1 = i2-1;
            if(i2+size-1 > N-1){         //设置子序列2的上界
                j2 = N-1;
            }
            else j2 = i2+size-1;
            Merge(l,Temp,i1,j1,i2,j2,&k);  //合并相邻两个子序列
            i1 = j2+1;                        //确定下一次合并第一个子序列的下界
        }
        for(i = 0;i < k;i ++){
            l[i] = Temp[i];
        }
        size *= 2;                            //子序列长度扩大一倍
    }
}

堆排序

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
typedef struct heap{
    int n;
    int *data;
}heap;


/**向下调整为最大堆**/
void AdjustHeap(int Heap[],int s,int m){
    int temp = Heap[s];
    for(int j = 2*s+1;j <= m; j *= 2){
        if(j < m &&Heap[j] < Heap[j+1]) j++;
        if(temp > Heap[j]) break;
        Heap[s] = Heap[j];
        s = j;
    }
    Heap[s] = temp;
}

/**建堆**/
void CreateHeap(int *heap,int n){
    int i;
    for(i = (n-2)/2;i >= 0;i --) AdjustHeap(heap,i,n);
}

/**堆初始化**/
void heapInit(heap *hp,int *a,int n){
    hp->n = n;
    hp->data = (int *)malloc( sizeof(int) *n);
    int i;
    for( i = 0;i < n;i ++) hp->data[i] = a[i];
    CreateHeap(hp->data ,N-1);
}

/**堆排序**/
void HeapSort(heap *hp){
    int i;
    for( i=hp->n/2 ; i>0 ;i--) AdjustHeap(hp->data,i,hp->n);
    for( i = hp-> n-1 ;i>0;i--){
        Swap( hp->data,0,i);
        AdjustHeap(hp->data,0,i-1);
    }
}

▲向下调整法====> 建堆 … 给一堆数据,一次性建堆

▲向上调整法====> 在已经是最小或最大堆的基础上,增加一个节点,仍保持为最大或最小堆

总体代码

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 100000


void RandCreate(int *a){
    int i;
    for ( i = 0; i < N; ++i)
        a[i] = 1 + (rand()%1000);
}

/***交换数组中,两个下标的值***/
void Swap(int *a,int i,int j){
    int tmp;
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}


/**简单选择排序**/
void SelectSort(int *l){
    int minx,i,j;
    for (i= 0; i < N-1; ++i){
        minx = i;   //默认标记为每次第一位元素下标
        for (j = i+1; j < N; ++j) if( l[minx] > l[j] ) minx = j;
        if( minx != i) Swap(l,minx,i); //判断起始位置是否为最小值
    }
}

/**直接插入排序**/
void InsertSort(int *l){
    int i,j;                                 //i标识待插入元素下标
    for(i = 1;i < N;i ++){
        int insertItem = l[i];              //标记每次第一位元素
        for(j = i-1;j >= 0;j --){
            //不断将有序序列中元素向后移动,为待插入元素空出一个位置
            if(insertItem < l[j]) l[j+1] = l[j];
            else break;
        }
        l[j+1] = insertItem;          //待插入元素有序存放至有序序列中
    }
}

/**冒泡排序**/
void BubbleSort(int *l){
    int i,j;
    //i标识每趟排序范围最后一个元素下标,每趟排序元素下标范围是0~i
    for(i = N-1;i > 0;i --){
        int isSwap = 0;         //教材错误,应该放到第二层循环前
        for(j = 0; j<i;j ++){
            if(l[j] > l[j+1]){
                Swap(l,j,j+1);
                isSwap = 1;
            }
        }
        if(!isSwap) break;
        //如果本趟排序没有发生元素交换,则直接可以认为排序已完成
    }
}


/**快速排序**/
//序列划分方法
int Partition(int *l,int low,int high){
    int i = low,j = high + 1;
    int pivot = l[low];                 //pivot是分割元素
    do{
        do i++;
        while(l[i] < pivot);      //i前进
        do j--;
        while(l[j] > pivot);      //j前进
        if(i < j) Swap(l,i,j);
    }while(i < j);
    Swap(l,low,j);
    return j;                                   //此时j是分割元素下标
}


//快速排序
void QuickSort(int *l,int low,int high){   //快速排序的递归函数
    int k;
    if(low < high){                            //当前待排序序列至少包含2个元素
        k = Partition(l,low,high);
        QuickSort(l,low,k-1);
        QuickSort(l,k+1,high);
    }
}


void QSort(int *l){
    //快速排序算法的主调用函数
    QuickSort(l,0,N-1);
}
/**快速排序**/


/**两路合并排序**/
//Merge函数
void Merge(int *l,int Temp[],int i1,int j1,int i2,int j2,int *k){
    int i = i1,j = i2;
    while((i <= j1)&&(j<=j2)){                       //若两个子序列都不空,则循环
        if(l[i] <= l[j]){
            Temp[(*k)++] = l[i++];         //将较小元素存入Temp[*k]
        }
        else Temp[(*k)++] = l[j++];
    }
    while(i <= j1) Temp[(*k)++] = l[i++];  //将子序列1中剩余元素存入Temp
    while(j <= j2) Temp[(*k)++] = l[j++];  //将子序列2中剩余元素存入Temp
}


//MergeSort函数
void MergeSort(int *l){
    int Temp[N];
    int i1,j1,i2,j2,i,k,size = 1;              //i1,j1和i2,j2分别是两个子序列的上,下界
    while(size < N){
        i1 = 0;
        k = 0;
        while(i1+size < N){              //若i1+size < n,则说明存在两个子序列,需要再两两合并
            i2 = i1+size;                      //确定子序列2的下界和子序列1的上界
            j1 = i2-1;
            if(i2+size-1 > N-1){         //设置子序列2的上界
                j2 = N-1;
            }
            else j2 = i2+size-1;
            Merge(l,Temp,i1,j1,i2,j2,&k);  //合并相邻两个子序列
            i1 = j2+1;                        //确定下一次合并第一个子序列的下界
        }
        for(i = 0;i < k;i ++){
            l[i] = Temp[i];
        }
        size *= 2;                            //子序列长度扩大一倍
    }
}
/**两路合并排序**/


/*****堆排序*****/
typedef struct heap{
    int n;
    int *data;
}heap;


/**向下调整为最大堆**/
void AdjustHeap(int Heap[],int s,int m){
    int temp = Heap[s];
    for(int j = 2*s+1;j <= m; j *= 2){
        if(j < m &&Heap[j] < Heap[j+1]) j++;
        if(temp > Heap[j]) break;
        Heap[s] = Heap[j];
        s = j;
    }
    Heap[s] = temp;
}

/**建堆**/
void CreateHeap(int *heap,int n){
    int i;
    for(i = (n-2)/2;i >= 0;i --) AdjustHeap(heap,i,n);
}

/**堆初始化**/
void heapInit(heap *hp,int *a,int n){
    hp->n = n;
    hp->data = (int *)malloc( sizeof(int) *n);
    int i;
    for( i = 0;i < n;i ++) hp->data[i] = a[i];
    CreateHeap(hp->data ,N-1);
}

/**堆排序**/
void HeapSort(heap *hp){
    int i;
    for( i=hp->n/2 ; i>0 ;i--) AdjustHeap(hp->data,i,hp->n);
    for( i = hp-> n-1 ;i>0;i--){
        Swap( hp->data,0,i);
        AdjustHeap(hp->data,0,i-1);
    }
}
/*****堆排序*****/


int main(){
    srand(time( NULL ));
    int a[6][N];
    int i,j;
    RandCreate(a[0]);
    for (int i = 1; i < 6; ++i)
        for (int j = 0; j < N; ++j)
            a[i][j] = a[0][j];

    double start1 = (double) clock();
    SelectSort(a[0]);
    double end1 = (double) clock();
    double diff1 = difftime(end1,start1);
    printf("%18s%10lf\n","简单选择排序时间:",diff1);

    double start2 = (double) clock();
    InsertSort(a[1]);
    double end2 = (double) clock();
    double diff2 = difftime(end2,start2);
    printf("%18s%10lf\n","直接插入排序时间:",diff2);

    double start3 = (double) clock();
    BubbleSort(a[2]);
    double end3 = (double) clock();
    double diff3 = difftime(end3,start3);
    printf("%18s%10lf\n","冒泡排序时间:",diff3);

    double start5 = (double) clock();
    MergeSort(a[4]);
    double end5 = (double) clock();
    double diff5 = difftime(end5,start5);
    printf("%18s%10lf\n","两路排序时间:",diff5);

    double start4 = (double) clock();
    QSort(a[3]);
    double end4 = (double) clock();
    double diff4 = difftime(end4,start4);
    printf("%18s%10lf\n","快速排序时间:",diff4);

    heap hp;
    heapInit(&hp,a[5],N);
    double start6 = (double) clock();
    HeapSort(&hp);
    double end6 = (double) clock();
    double diff6 = difftime(end6,start6);
    printf("%18s%10lf\n","堆排序时间:",diff6);

    system("pause");
    return 0;
}

关于堆排序的理解

限选课对堆排的没有要求,但是在实验中涉及了。平时也没怎么看过堆排序，所以这次写的时候出现了理解上的错误，在此记下：

向上和向下调整法的区别:

区别在于用途不一样，而不是 生成最小堆和最大堆的区别

  • 向下调整法====> 建堆 … 给一堆数据,一次性建堆

  • 向上调整法====> 在已经是最小或最大堆的基础上,增加一个节点,仍保持为最大或最小堆

具体而言：

给定一个乱序的数组，要构建最小或最大堆==> 向下调整

已经是个最大或最小堆的数组,插入或删除一个元素，仍要保持最小堆 ;优先权队列===> 向上调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//最大堆
void AdjustHeap(int Heap[],int s,int m){
    int temp = Heap[s];
    for(int j = 2*s+1;j <= m; j *= 2){
        if(j < m &&Heap[j] < Heap[j+1]){
            j++;
        }
        if(temp > Heap[j]){
            break;
        }
        Heap[s] = Heap[j];
        s = j;
    }
    Heap[s] = temp;
}

区别在于第5行和第8行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//最小堆
void AdjustHeap(int Heap[],int s,int m){
    int temp = Heap[s];
    for(int j = 2*s+1;j <= m; j = j*2+1){
        if(j < m &&Heap[j] > Heap[j+1]){
            j++;
        }
        if(temp < Heap[j]){
            break;
        }
        Heap[s] = Heap[j];
        s = j;
    }
    Heap[s] = temp;
}

建堆的执行过程大致是: CreateHeap函数从下往上建，即从[s,m]==>[s-1,m],在保证从s到m是最小堆后,再用向下调整法使[s-1,m]也成为堆。

向下调整的过程： 从s–>m,依次调整

总的逻辑是，由于要使左子树和右子树满足要求，所以需要从下往上调整。

Author: Mrli

Link: https://nymrli.top/2018/12/28/数据结构实验4——各种内排序算法的实现及性能比较/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
数据结构实验2——二叉树的基本操作及哈夫曼编码译码系统的实现NextPost >
南邮《信号与系统B》复习知识点大纲
CATALOG
  1. 1. 部分代码
    1. 1.1. 辅助函数
    2. 1.2. 直接插入排序
    3. 1.3. 冒泡排序
    4. 1.4. 快速排序
    5. 1.5. 两路合并排序
    6. 1.6. 堆排序
  2. 2. 总体代码
  3. 3. 关于堆排序的理解