一、冒泡排序
冒泡排序算是最基础的一种算法了,复杂度为O(N^2),其基本思想是:从最低端数据开始,两两相邻比较,如果反序则交换。代码如下:
/*最基本的冒泡排序*/ void BubbleSort1 (int n, int *array) /*little > big*/ { int i, j; for (i=0; i<n-1; i++) { for (j=n-1; j>i; j--) { if (array[j] < array[j-1]) { int temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; } } } }
优化:例如序列{2,1,3,4,5,6,7,8,9},当i=1时,整个序列已然有序,但是还是会进行i=3,4,5,6,7,8,9的循环,可以从此处进行优化,如果某一次冒泡未发生数据交换,则证明整个序列已然有序,之后不需要继续循环。通过设置flag变量实现,代码如下:
void BubbleSort2 (int n, int *array) { int i, j, flag=1; /*flag=1表示需要继续冒泡*/ for (i=0; i<n-1 && flag; i++) { flag = 0; for (j=n-1; j>i; j--) { if (array[j] < array[j-1]) { int temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; flag = 1; } } } }
二、简单选择排序
冒泡排序是相邻元素比较交换,而简单选择排序是只比较不交换,只有遍历一遍找出最小(大)值,再与前面的交换,其时间复杂度是O(N^2),代码如下:
void SelectSort (int n, int *array) { int i, j, min; for (i=0; i<n-1; i++) { min = i; for (j=i+1; j<n; j++) { if (array[min] > array[j]) min = j; } int temp = array[min]; array[min] = array[i]; array[i] = temp; } }
三、直接插入排序
直接插入排序的基本思想是:将一个数插入到有序列表的合适位置,从而得到新的有序列表。其时间复杂度是O(N^2),代码如下
void InsertSort (int n, int*array) { int i, j; for (i=1; i<n; i++) { if (array[i] < array[i-1]) /*是否需要插入*/ { int key = array[i]; //哨兵 for (j = i-1;j>=0 && array[j] > key; j--) { array[j+1] = array[j]; } /*循环结束时array[j]<=key,将key插入到j+1处*/ array[j+1] = key; } } }
总结:冒泡排序,简单选择排序,直接插入排序的时间复杂度都是O(N^2),但整体上直接插入排序>简单选择排序>,冒泡排序。
排序算法学习之简单排序(冒泡排序,简单选择排序,直接插入排序),布布扣,bubuko.com
排序算法学习之简单排序(冒泡排序,简单选择排序,直接插入排序)
原文:http://www.cnblogs.com/lifan/p/3718449.html