冒泡排序是计算机中比较简单的一种排序方法,他是一种稳定的排序方法.
原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,
这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束
1 void bubble_sort(int arr[], int count) 2 { 3 int i, j, tmp; 4 5 for (i = 0; i < count-1; i++) 6 { 7 for (j = i+1; j < count; j++) 8 { 9 if (arr[i] > arr[j]) 10 { 11 tmp = arr[i]; 12 arr[i] =arr[j]; 13 arr[j] = tmp; 14 } 15 } 16 } 17 }
空间复杂度:O(1)
时间复杂度:O(n2)
简单排序跟冒泡排序的思想是一致的,不同的是简单排序是记录最小(大)值的位置,最后才交换一次,比冒泡排序少了许多次交换
1 void simple_selection_sort(int arr[], int count) 2 { 3 int i, j, k, tmp; 4 5 for (i = 0; i < count-1; i++) 6 { 7 k = i; 8 9 for (j = i+1; j < count; j++) 10 { 11 if (arr[k] > arr[j]) 12 { 13 k = j; 14 } 15 } 16 if (k != i) 17 { 18 tmp = arr[i]; 19 arr[i] = arr[k]; 20 arr[k] = tmp; 21 } 22 } 23 }
空间复杂度:O(1)
时间复杂度:O(n2)
虽然冒泡排序的时间复杂度也是O(n2), 但是简单选择排序的性能还是比冒泡更好一些.
把N个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素(a[0])，无序表中包含有(N-1)个元素(a[1]~a[N-1]).
排序过程中每次从无序表中取出第一个元素(a[i] (i >=1))，将它插入到有序表(a[0] ~ a[i - 1])中的适当位置，使之成为新的有序表，重复N-1次可完成排序过程。
具体的插入方法是:先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1].
1 void straight_insertion_sort(int arr[], int count) 2 { 3 int i, j, tmp; 4 5 for (i = 1; i < count; i++) /* N-1次操作 */ 6 { 7 tmp = arr[i]; /* 哨兵 */ 8 j = i - 1; 9 while (j >= 0 && tmp < arr[j]) 10 { 11 arr[j+1] = arr[j]; /* 右移 */ 12 j--; 13 } 14 arr[j+1] = tmp; /* 插入 */ 15 } 16 }
空间复杂度:O(1)
时间复杂度:O(n2)
虽然冒泡排序与简单选择排序的时间复杂度都是O(n2), 但是直接插入排序的性能还是比这2个更好一些.
希尔排序又称为“缩小增量排序”。其基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，
然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比直接插入排序有较大提高。
1 /* left,right 为数组的下标 */ 2 void quick_sort(int *a, int left, int right) 3 { 4 int i = left; 5 int j = right; 6 int key = a[left]; 7 8 if (left >= right) 9 {/* 如果左边的数组大于或者等于就代表已经成分组 */ 10 return; 11 } 12 13 while (i < j) /* i=j表示left到right元素已经完成分组 */ 14 { 15 /* 向前寻找 */ 16 while (i < j && key <= a[j]) 17 /* 寻找结束的条件是:1.找到一个小余或者大于key的数（大小取决于你想升 18 序还是降序）2.没有符合的则i与j相遇 */ 19 { 20 j--; 21 } 22 a[i] = a[j]; /* 找到一个这样的数后就把它赋给前面的被拿走的i的值 */ 23 24 25 /* 向后寻找 */ 26 while (i < j && key >= a[i]) 27 { 28 i++; 29 } 30 a[j] = a[i]; 31 } 32 /* 此时 i = j */ 33 34 a[i] = key;/* 当在当组内找完一遍以后就把中间数key回归 */ 35 quick_sort(a, left, i - 1);/* 最后用同样的方式对分出来的左边的小组进行同上的做法 */ 36 quick_sort(a, i + 1, right);/* 用同样的方式对分出来的右边的小组进行同上的做法 */ 37 /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/ 38 }
空间复杂度:O(log2n)
时间复杂度:O(log2n)
视频教程:http://www.iqiyi.com/v_19rrhzyeqs.html
原文：http://www.cnblogs.com/LubinLew/p/4468429.html
