常见排序算法（C语言实现）_c语言排序算法实现

个人学习记录：常见排序算法的C语言实现

#include<stdio.h>

// 调试打印函数
void Print(int a[]);

// 插入排序
void insert_sort(int a[]);

// 选择排序
void select_sort(int a[]);

// 冒泡排序
void bubble_sort(int a[]);

// 快速排序
void quick_sort(int a[], int left, int right);
void Qsort(int a[], int left, int right);

// 堆排序
void Heap_sort(int a[], int length); 

// 归并排序
void Merg_sort(int a[], int first, int last, int temp[]);

// 希尔排序
void shell_sort(int a[], int n);


const int n = 10;
int temp[n]; //归并排序用的临时数组

int main()
{
	// int arr[n] = {3,4,1,2,9,5,31,21,12,8};
	int arr[n] = {49,38,65,97,76,13,27,49,55,04};
    
    Print(arr);
	// insert_sort(arr);
	// select_sort(arr);
	// bubble_sort(arr);
	// quick_sort(arr,0,n-1);
	// Qsort(arr,0,n-1);
	// Heap_sort(arr, n);
	// Merg_sort(arr,0,n,temp);
    shell_sort(arr,n);
    Print(arr);
}

void Print(int a[])
{
    for(int i = 0 ; i<n ; i++)  printf("%d ",a[i]);
    printf("\n");
}

//插入排序 
void insert_sort(int a[])
{
    int i , j , k;
    for(i = 1; i < n ; i++)
    {
        //在已排好序的序列中插入，移动大于当前数k的其他数
        for( j = i-1, k = a[i] ; j>=0 && k <a[j] ; j-- )
        {
            a[j+1] = a[j];
        }
        a[j+1] = k;
    }
    printf("插入排序: ");
    Print(a);
}

//选择排序 
void select_sort(int a[])
{
    for( int i =0 ; i< n-1 ; i++)
    {
        int k = i;
        for(int j = i+1 ; j<n ; j++)
        {
            //在i...n中，选最小的元素
            if(a[k] > a[j]) k = j;
        }
        if(k!=i)
        {
            int tmp = a[i];
            a[i] = a[k];
            a[k] = tmp;
        }
    }
    printf("选择排序: ");
    Print(a);
}

//冒泡排序 
void bubble_sort(int a[])
{
    for(int i = 0 ; i < n-1 ; i++)
    {
        for(int j = i+1 ; j<n ; j++)
        {
            if(a[i] > a[j])
            {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
    }
    
    printf("冒泡排序: ");
    Print(a);
}

//快速排序1 
void quick_sort(int a[], int left, int right)
{
	if(left>right)	return;
	int i, j, t, temp;
	i = left;
	j = right;
	temp = a[i];
	while( i != j )
	{
		while( a[j] >= temp && i < j ) j--;
		while( a[i] <= temp && i < j ) i++;
		if( i < j )
		{
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	a[left] = a[i];
	a[i] = temp;
	quick_sort(a,left,i-1);
	quick_sort(a,i+1,right);
}

//快速排序2 
int Partition(int a[], int low, int high)
{
	int p = a[low];
	while(low < high)
	{
		while(low < high && a[high] >= p) high--;
		if(low < high) a[low] = a[high];
		while(low < high && a[low] <= p) low++;
		if(low < high) a[high] = a[low];
	}
	a[low] = p;
	return low;
}
void Qsort(int a[], int low, int high)
{
	if(low < high)
	{
		int q = Partition(a,low,high); //将数组一分为二 
		Qsort(a,low,q-1);	//对低子表递归排序 
		Qsort(a,q+1,high);	//对高子表递归排序 
	}
}

//堆排序
void heapAdjust(int a[], int i, int nlength)
{
    int nchild;  //保存子节点的下标
    for( int nTemp = a[i] ; 2*i+1 < nlength ; i = nchild)
    {
        //子节点位置
        nchild = 2*i+1;
        //选择较大的子节点
        if( nchild < nlength-1 && a[nchild] < a[nchild+1] )
            nchild++;
        //如果较大子节点大于其父节点，则交换
        if(nTemp < a[nchild] )
        {
            a[i] = a[nchild];
            a[nchild] = nTemp;
        }
        else break;
    }
}
void Heap_sort(int a[], int length)
{
    //调整前半部分元素，使第一个元素是最大的
	for(int i = length/2-1 ; i >= 0 ; i--)
		heapAdjust(a, i ,length);
	//从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
	for( int i = length-1 ; i >= 0 ; i--)
	{
	    // 把第一个元素和当前的最后一个元素交换。
	    // 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
		int tmp = a[i];
		a[i] = a[0];
		a[0] = tmp;
		// 不断缩小调整heap的范围，每一次调整完毕，保证第一个元素是当前序列的最大值
		heapAdjust(a, 0, i);
	}
}

//归并排序
void Mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid+1;
    int m = mid, n = last;
    int k = 0;
    while(i<=m && j<=n)
    {
        if(a[i] <= a[j])  temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while(i <= m)  temp[k++] = a[i++];
    while( j <= n)  temp[k++] = a[j++];
    for(i = 0; i<k ; i++)   a[first+i] = temp[i];
}
void Merg_sort(int a[], int first, int last, int temp[])
{
        if( first < last)
        {
            int mid = (first + last) / 2;
            Merg_sort(a, first, mid, temp);  //左边有序
            Merg_sort(a, mid+1,last,temp);   //右边有序
            Mergearray(a, first, mid, last, temp);  //合并
        }
}

//希尔排序，选择排序的优化
void shell_sort(int a[], int n)
{
    int s, i, j, temp;  //s为增量, 初始取数组长度的一半
    for(s = n/2 ; s >= 1 ;s /= 2)
    {
        for( i = s ; i<n ; i++)
        {
            temp = a[i] ;
            for( j = i-s; ( j >=0 ) && ( a[j] > temp ) ; j-=s )
            {
                a[j+s] = a[j];
            }
            a[j+s] = temp;//交换前后值完成
        }
    }
}
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
236
237
238
239
240
241
242
243