排序算法

冒泡排序

　　基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。

 1 void BubbleSort(int array[], int len) // O(n*n)
 2 {
 3     int i = 0;
 4     int j = 0;
 5     int exchange = 1; //表明数组是否已经排好序 已经排好序为0   1表示没有排好序
 6     for (i = 0; (i<len) && exchange; i++)
 7     {
 8         exchange = 0;//认为已经排序完毕
 9         for (j = len - 1; j>i; j--)
10         {
11             if (array[j] < array[j - 1])
12             {
13                 swap(array, j, j - 1);
14                 exchange = 1;//
15             }
16         }
17     }
18 }

选择排序

　　基本思想：

　　在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
　　第二次遍历n-2个数，找到最小的数值与第二个元素交换；
　　。。。
　　第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

 1 void SelectionSort(int array[], int len) // O(n*n)
 2 {
 3     int i = 0;
 4     int j = 0;
 5     int minIndex = -1;
 6 
 7     for (i = 0; i<len; i++)
 8     {
 9         minIndex = i; //寻找最小元素的下标
10         for (j = i + 1; j<len; j++)
11         {
12             if (array[j] < array[minIndex]) //开始寻找最小元素的下标
13             {
14                 minIndex = j;
15             }
16         }
17         if (minIndex != i) {
18             swap(array, i, minIndex);
19         }
20     }
21 }

插入排序

　　基本思想：在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。

　　如此反复循环，直到全部排好顺序。

 1 void insert_sort(int array[], int len)
 2 {
 3     int temp;
 4     int i, j;
 5     for(int i = 0; i < len - 1; i++)
 6         for(int j = i+1; j > 0; j--)
 7             if (array[j] < array[j - 1])
 8             {
 9                 temp = array[j];
10                 array[j] = array[j - 1];
11                 array[j - 1] = temp;
12             }
13             else {
14                 break;
15             }
16 
17 }