排序算法总结

一、冒泡排序

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3.针对所有的元素重复以上的步骤，除了最后一个；
4.重复步骤1~3，直到排序完成。

java实现：

public static int array[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

   public static void main(String args[]){
       bubbleSort();
   }
   public static void bubbleSort(){
       int length = array.length;
       for (int i = 0; i < length; i++) {
           for (int j = 0; j < length - 1 - i; j++) {
               if(array[j] > array[j+1]){            //相邻元素两两对比
                   array[j] = array[j] ^ array[j+1];  //元素交换
                   array[j+1] = array[j] ^ array[j+1];
                   array[j] = array[j] ^ array[j+1];
               }
           }
       }
       System.out.println(Arrays.toString(array));
   }

输出：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

冒泡排序的两种改进方式：
1.维护一个pos变量，记录每次遍历最后交换元素的位置，因为最后交换的位置之后都是已排序好的，下一次遍历可以以pos为终点。减少不必要的比较。
2.记录一次遍历中有没有发生元素的交换，如果没有，可以直接结束排序。
算法分析
最佳情况：T(n) = O(n) 当输入的数据已经是正序时
最差情况：T(n) = O(n2)当输入的数据是反序时
平均情况：T(n) = O(n2)

二、选择排序

1.遍历数组，找到最大（小）元素，与遍历的第一个元素交换。
2.遍历开始元素位置后移一位，重复步骤1。
java实现：

    public static int array[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

    public static void main(String args[]){
        selectSort();
    }

    public static void selectSort(){
        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            int minPos = i;
            for (int j = i + 1; j < length; j++) {
                if(array[minPos] > attr[j]){
                    minPos = j;
                }
            }
            if(minPos != i){
                array[minPos] ^= array[i];
                array[i] ^= array[minPos];
                array[minPos] ^= array[i];
            }
        }
        System.out.println(Arrays.toString(array));
    }

算法分析
最佳情况：T(n) = O(n2)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)

三、插入排序

1.选一个未排序的元素，从后往前遍历已排序的数组，当发现小于等于一个元素时，插入到这元素的后面，同时后面的元素整体往后挪一位。
java实现：

    public static void insertSort(){
        int length = array.length;
        for (int i = 1; i < length; i++) {//默认第一个元素是已排序的，从第二个开始插入
            int key = array[i];
            int j = i - 1;
            while(j >= 0 &&array[j] > key){
                array[j+1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
        System.out.println(Arrays.toString(array));
    }

改进方式：使用二分查找确定插入位置
算法分析
最佳情况：输入数组按升序排列。T(n) = O(n)
最坏情况：输入数组按降序排列。T(n) = O(n2)
平均情况：T(n) = O(n2)

四、希尔排序

定义：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
java实现：

    public static void shellSort(){
        int length = array.length;
        int gap = 1;
        while(gap < length/5){
            gap = gap*5+1;
        }
        for (;gap > 0; gap/=2){
            for (int i = gap; i < length; i++) {
                int key = array[i];
                int j = i - gap;
                while(j >= 0&&array[j]>key){
                    array[j+gap] = array[j];
                    j -= gap;
                }
                array[j+gap] = key;
            }
        }
        System.out.println(Arrays.toString(array));
    }

排序过程

算法分析
最佳情况：T(n) = O(nlog2 n)
最坏情况：T(n) = O(nlog2 n)
平均情况：T(n) = O(nlog n)

五、归并排序

(1)定义：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
(2)算法描述和实现
具体算法描述如下：

1.把长度为n的输入序列分成两个长度为n/2的子序列；
2.对这两个子序列分别采用归并排序；
3.将两个排序好的子序列合并成一个最终的排序序列。

public static int[] mergeSort(int[] array){
        int length = array.length;
        if(length < 2){
            return array;
        }
        return merge(mergeSort(Arrays.copyOf(array,length/2)),mergeSort(Arrays.copyOfRange(array,length/2,length)));
    }

    public static int[] merge(int[] left,int[] right){
        int leftLength = left.length;
        int rightLength = right.length;
        int totalLength = leftLength + rightLength;
        int[] result = new int[totalLength];
        int l=0;
        int r=0;
        for (int i = 0; i < totalLength; i++) {
            if(l == leftLength){
                result[i] = right[r];
                ++r;
            }else if(r == rightLength){
                result[i] = left[l];
                ++l;
            }else if(left[l]<right[r]){
                result[i] = left[l];
                ++l;
            }else if(right[r] < left[l]) {
                result[i] = right[r];
                ++r;
            }
        }
        return result;
    }

(3) 算法分析
最佳情况：T(n) = O(n)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)

六、快速排序

(1) 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
(2) 步骤：（正序）
1.选取一个基数。
2.从后往前遍历，直到找到小于基数的元素，交换low和high。
3.从前往后遍历，直到找到大于基数的元素，交换low和high。
4.第2第3步循环执行，直到low>=high，把基数放到low中，此时，基数左边的数比基数小，右边的数都比基数大。接着对左边和右边分别排序。
java实现：

    public static void quicklySort2(int[] arr,int left,int right){
        if(left >= right)//如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了
            return;
        int key = arr[left];//以第一个元素为基准
        int l = left,h = right;
        while (l < h){//控制在当组内寻找一遍
            while (l<h && arr[h] > key){//循环直到找到一个小于或者大于key的数（大于或小于取决于你想升序还是降序）
                h--;//向前查找
            }
            arr[l] = arr[h];//找到一个这样的数后就把它赋给前面的被拿走的l的值
            while (l<h && arr[l] < key){
                l++;
            }
            arr[h] = arr[l];
        }
        arr[l] = key;//基准值归位
        quicklySort2(arr,left,l-1);
        quicklySort2(arr,l+1,right);
    }

(3) 算法分析
最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(nlogn)