首页 > 代码库 > 排序系列之——冒泡排序、插入排序、选择排序
排序系列之——冒泡排序、插入排序、选择排序
排序之——冒泡排序：
基本思想：假设待排序表长为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("\n");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:\n");66 print_Arr(arr, N);67 68 BubbleSort(arr, N);69 printf("After\n");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("\n");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:\n");53 print_Arr(arr, N);54 55 InsertSort(arr, N);56 printf("After\n");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 20void print_Arr(int *arr, int len){ int i; for (i = 0; i < len; ++i) { printf("%4d", arr[i]); } printf("\n");}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:\n"); print_Arr(arr, N); SelectSort(arr, N); printf("After\n"); print_Arr(arr, N); return 0;}
性能分析： 空间复杂度O(1),最坏情况下时间复杂度为O(N*N)，最好情况下（表中元素基本有序）时间复杂度为O(N)，其平均时间复杂度为O(N*N)；
稳定性：简单排序是一个不稳定的排序方法。
其余排序详见 排序系列之——快速排序、堆排序、合并排序
排序系列之——冒泡排序、插入排序、选择排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。