十大排序总结

1. 冒泡排序(平均时间复杂度为O(n^2) ,最好情况为顺序 O(n) ,最坏为逆序O(n^2),空间复杂度为O(1)
   （1）改进后的冒泡排序算法：

void BubbleSort2( Sqlist *L)
{
    int i , j;
    Status flag = true;     //用来作标记，当交换时设为true，
    for(i = 1; i < L->Length && flag; i++ ){
       flag = false;   //初始值为false;
       for( j = L ->Length - 1 ; j >= i; j--)
       {
            if(L -> r[j] > L -> r[j+1])
            {
                 swap(L, j, j+1);
                 flag = true;
             } 
        }
    }  
}

2. 快速排序：
   其主要原理是每次都能确定一个元素的确定位置。
   时间复杂度 好情况(无序) O(nlog2n)；坏情况(有序)O(n^2)
   每次Partition O(n^2)快速排序，是一种不稳定的排序，其空间复杂度是 O(log2n)
   ，因为需要空间来保存递归的区间范围。

递归实现：使用的是系统栈，如果用非递归需要自己构建栈

 public static int partion(int[] array, int low, int high){

        int temp = array[low];
        while(low < high){
            while(low < high && array[high] > temp){
                --high;
            }
            if(low >= high){
                break;
            }else{
                array[low] = array[high];
            }
            while (low < high && array[low] <= temp){
                ++low;
            }
            if (low >= high ){
                break;
            }else{
                array[high] = array[low];
            }
        }
        array[low] = temp;
        System.out.println(Arrays.toString(array));
        return low;
    }
    public static void Quick(int[] array, int start, int end){
        int par = partion(array, start, end);

        if(par > start + 1) {
           Quick(array, start,par -1);
        if (par < end - 1) {
           Quick(array, par +1, end);
    }

3. 选择排序（第i 个元素 比较 n-i趟，总共需n(n-1)/2次，对于交换次数，顺序下最好的为0次，逆序下交换n-1次。最终时间复杂度为O(n^2) , 空间复杂度为O(1),还是优于冒泡排序）

void SelectSort(Sqlist *L){
     int  i, j, min;
     for( i = 1; i < L->Length ; i++){
            min = i;
            for(j = i + 1; j <= L->Length ; j++){
                   if(L ->r[min] > L->r[j]){
                       min = j;   //找到最小值
                  }
                  if( i != min)
                        swap(L , i , min);//找到最小值与r[i]交换
            }
      }
}

4. 插入排序（在一个已知有序中，插入一个新的记录使其仍然有序）最好情况为有序，只需要比较n-1次，不需要移动，时间复杂度为O(n),最坏情况为逆序，比较(n+2)(n-1)/2次，移动（n+4)(n-1)/2次。时间复杂度为O(n^{2);随机序列时间复杂度为O(n}2); 插入排序比选择排序和冒泡排序都要好。

insertSort(int [] a)
{
      int n = a.length;
      int i , j;
      for(i = 1; i < n; i++){
           //temp为本次插入有序列表中的数；
           int temp = a[i];   
           //寻找temp插入有序序列表的正确位置/
           for( j = i - 1; j >= 0 && a[j] > temp ; j--){
                   //元素后移， 为插入temp做准备；
                   a[j + 1] = a[j];
           }
           a[j + 1] = temp; //插入temp；
      }
}