排序--简单排序

一、冒泡排序

原理：从第一个元素开始遍历比较，如果相邻元素大于它，就做一次交换，冒泡完成的元素不参与下一次比较，由此可见越往后的元素需要比较的次数递减，for循环可实现。

源代码：

void bubble_sort(int *array, int size_array) {     for(int j = size_array ; j >= 0; j--)     {         int flag = 0;         for(int i = 0; i< j; i++)         {             if(array[i] > array[i + 1])             {                 swap(&array[i],&array[i+1]);                 flag = 1;             }         }         if(flag == 0) break;     } }   二、插入排序 原理：从第二个元素开始向前比较判断，如果比前一个元素小，则前一个元素往后移动一位，直到第一个元素或者前面条件不成立，将该元素插入当前位置。 源代码： void insertion_sort(int *array, int size_array) {     for(int j = 1 ;j <=size_array; j++)     {         int i = j;         int temp = array[j];         for(; i > 0 && temp < array[i - 1]; i--)             array[i] = array[i - 1];         array[i] = temp;     } }   三、选择排序 原理：可以简单理解为冒泡的逆过程，从第一个元素开始，找出所有元素的最小值，将最小值和第一个元素交换，依次类推，从第二个第三个做同样的操作，最后得到一个有序序列 源代码： void selection_sort(int *array, int size_array) {     for(int i = 0; i < size_array; i++)     {         int min_position = i;         for(int j = i; j< size_array; j++)         {             if(array[min_position] > array[j])             min_position = j;
        }         swap(&array[i],&array[min_position]);     } }       四、希尔排序 原理：可以看作是插入排序的升级，前两种排序最坏时间复杂度都是O(N^2)，希尔排序不采用相邻两个元素之间进行比较插入，而是选择有一定间隔的元素之间进行比较插入，原因是为了能一次消除多个逆序对，减少时间复杂度，间隔的大小按规则减小，直到间隔为1进行一次插入排序，得到有序的元素序列。 关键：选取增量序列 源代码： void shell_sort(int *array, int size_array) {     int N = (size_array + 1)/2;     for(int k = N; k > 0; k /= 2)     {         for(int j = k ;j <=size_array; j++)         {             int i = j;             int temp = array[j];             for(; i > k - 1 && temp < array[i - k]; i -= k)                 array[i] = array[i - k];             array[i] = temp;         }     } }