排序之——冒泡排序：
基本思想：假设待排序表长为N，从后往前（或者从前往后）两两比较相邻元素的值，若为逆序（arr[i-1]>arr[i]），则交换他们，直到序列比较完。这时一趟冒泡。
代码如下：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #include <time.h> 5 #define N 20 6 7 void print_Arr(int *arr, int len) 8 { 9 int i; 10 for (i = 0; i < len; ++i) 11 { 12 printf("%4d", arr[i]); 13 } 14 printf(" "); 15 } 16 17 void init_Arr(int *arr, int len) 18 { 19 int i = 0; 20 while( i < len) 21 { 22 arr[i] = rand()%1000 ; 23 ++i; 24 } 25 } 26 27 void swap(int* left, int *right) 28 { 29 int tmp = *left; 30 *left = *right; 31 *right = tmp; 32 } 33 34 void BubbleSort(int *arr, int len) //双向冒泡，即一个来回确定 最顶端和最底端位置 35 { 36 int up = 0; 37 int down = len-1; 38 39 int i, j; //用于遍历 40 while( up <= down) 41 { 42 for(i = up; i < down; ++i) //将最大元素放置在末尾 43 { 44 if( arr[i] > arr[i+1]) 45 swap( &arr[i], &arr[i+1]); 46 } 47 --down ; 48 if(up == down) 49 break; 50 for(j = down; j > up; --j)//将最小元素放置在顶端 51 { 52 if(arr[j] < arr[j-1]) 53 swap(&arr[j], &arr[j-1]); 54 } 55 ++up; 56 } 57 } 58 59 int main(int argc, char const *argv[]) 60 { 61 srand(time(NULL)); 62 63 int arr[N]; 64 init_Arr(arr, N); 65 printf("Before: "); 66 print_Arr(arr, N); 67 68 BubbleSort(arr, N); 69 printf("After "); 70 print_Arr(arr, N); 71 return 0; 72 }
性能分析：
空间复杂度O(1),最坏情况下时间复杂度为O(N*N)，最好情况下（表中元素基本有序）时间复杂度为O(N)，其平均时间复杂度为O(N*N)；
稳定性：是一个稳定的排序方法。
排序之——插入排序：
基本思想：
1、依次将arr[1]~arr[len-1]插入到前面已排序序列
2、进行排序时，设置一个哨兵，用于保存每次要插入的元素（目的：减少交换次数）；
3、从后往前查找待插入的位置。
代码如下：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #include <time.h> 5 #define N 20 6 //打印函数 7 void print_Arr(int *arr, int len) 8 { 9 int i; 10 for (i = 0; i < len; ++i) 11 { 12 printf("%4d", arr[i]); 13 } 14 printf(" "); 15 } 16 //初始化函数 17 void init_Arr(int *arr, int len) 18 { 19 int i = 0; 20 while( i < len) 21 { 22 arr[i] = rand()%1000 ; 23 ++i; 24 } 25 } 26 //插入排序 27 void InsertSort(int *arr, int len) 28 { 29 if( len <=1 ) 30 return ; 31 32 int pos, index; 33 int key; 34 for( pos = 1; pos < len; ++pos) //依次将arr[1]~arr[len-1]插入到前面已排序序列 35 { 36 key = arr[pos];//复制为哨兵 37 for( index = pos-1; index >=0; --index) //找到要插入的位置 38 { 39 if(arr[index] > key) //从小到大排列 40 arr[index +1] = arr[index];//向后移动 41 else //找到要插入的位置 42 break; 43 } 44 arr[index+1] = key; 45 } 46 } 47 48 int main(int argc, char const *argv[]) 49 { 50 int arr[N]; 51 init_Arr(arr, N); 52 printf("Before: "); 53 print_Arr(arr, N); 54 55 InsertSort(arr, N); 56 printf("After "); 57 print_Arr(arr, N); 58 return 0; 59 }
性能分析： 空间复杂度O(1),最坏情况下时间复杂度为O(N*N)，最好情况下（表中元素基本有序）时间复杂度为O(N)，其平均时间复杂度为O(N*N)；
稳定性：插入排序是一个稳定的排序方法。
排序之——选择排序：
基本思想：每一趟在后面的n-i+1（i=1，2, 3···）个待排序列元素中选取一个最小的元素，作为有序子序列的第i个元素。
代码如下：
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define N 20 void print_Arr(int *arr, int len) { int i; for (i = 0; i < len; ++i) { printf("%4d", arr[i]); } printf(" "); } void init_Arr(int *arr, int len) { int i = 0; while( i < len) { arr[i] = rand()%1000 ; ++i; } } void swap(int* left, int *right) { int tmp = *left; *left = *right; *right = tmp; } void SelectSort(int *arr, int len) { int pos, minpos, index; for (pos = 0; pos <len; ++pos)//比较趟数 { minpos = pos;//设置每次最小值下标的初始值 for( index = pos+1; index < len; ++index) //依次与后面的各个元素比较 { if(arr[index] < arr[minpos]) minpos = index; } if( minpos != pos) //如果最小值下标发生了变化，交换之 swap(&arr[pos], &arr[minpos]); } } int main(int argc, char const *argv[]) { srand(time(NULL)); int arr[N]; init_Arr(arr, N); printf("Before: "); print_Arr(arr, N); SelectSort(arr, N); printf("After "); print_Arr(arr, N); return 0; }
性能分析： 空间复杂度O(1),最坏情况下时间复杂度为O(N*N)，最好情况下（表中元素基本有序）时间复杂度为O(N)，其平均时间复杂度为O(N*N)；
稳定性：简单排序是一个不稳定的排序方法。
其余排序详见 排序系列之——快速排序、堆排序、归并排序