常见排序算法

一、冒泡排序

算法描述

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

代码实现

public void bubbleSort(int[] arr){
    int temp;
    for (int i = arr.length-1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j]>arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

稳定性

在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序。

适用场景

冒泡排序思路简单，代码也简单，特别适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。

代码优化

在数据完全有序的时候展现出最优时间复杂度，为O(n)。其他情况下，几乎总是O( n2 )。因此，算法在数据基本有序的情况下，性能最好。
要使算法在最佳情况下有O(n)复杂度，需要做一些改进，增加一个swap的标志，当前一轮没有进行交换时，说明数组已经有序，没有必要再进行下一轮的循环了，直接退出。

public static void bubbleSort(int[] arr) {
    int temp = 0;
    boolean swap;
    for (int i = arr.length - 1; i > 0; i--) {
        swap=false;
        for (int j = 0; j < i; j++) { 
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swap=true;
            }
        }//loop j
        if (swap==false){
            break;
        }
    }//loop i
}

二、选择排序

选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。

算法描述

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

public void selectionSort(int[] arr){
    int temp, min = 0;
    for(int i = 0; i < arr.length; i++){
        min = i;
        for(int j = i; j < arr.length; j++){
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        if (min != i) {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

稳定性

用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的。
不过，一般提到排序算法时，大家往往会默认是数组实现，所以选择排序是不稳定的。

三、插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述

把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
重复上述过程直到最后一个元素被插入有序子数组中。

算法实现

public void insertionSort(int[] arr){
    for (int i=1; i<arr.length; i++){
        int value = arr[i];
        int position=i;
        while (position>0 && arr[position-1]>value){
            arr[position] = arr[position-1];
            position--;
        }
        arr[position] = value;
    }
}

适用场景

插入排序由于O(n2)的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。例如，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的实现中，当待排数组长度小于47时，会使用插入排序。

四、归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

两种方法

递归法（Top-down）

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

迭代法（Bottom-up）

原理如下（假设序列共有n个元素）：

将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
重复步骤2，直到所有元素排序完毕，即序列数为1

算法实现

public void mergeSort(int[] arr){
    int[] temp = new int[arr.length];
    internalMergeSort(arr, temp, 0, arr.length-1);
}
private void internalMergeSort(int[] arr, int[] temp, int left, int right){
    if(left<right){ //如果数组长度>1，则递归
        int mid = (left+right)/2;
        internalMergeSort(arr, temp, left, mid);
        internalMergeSort(arr, temp, mid+1, right);
        mergeSortedArray(arr, temp, left, mid, right); //合并两个子数组
    }
}
private void mergeSortedArray(int[] arr, int[] temp, int left, int mid, int right){
    //三个数组开始位置
    int i = left;
    int j = mid+1;
    int k = 0;
    while (i <= mid && j <= right){
        temp[k++] = arr[i] > arr[j] ? arr[i++] : arr[j++];
    }
    while(i <= mid){
        temp[k++] = arr[i++];
    }
    while(j <= right){
        temp[k++] = arr[j++];
    }
    for(i=0; i<right; i++){
        arr[left+i] = temp[i];
    }
}

稳定性

因为我们在遇到相等的数据的时候必然是按顺序“抄写”到辅助数组上的，所以，归并排序同样是稳定算法。

快速排序

快速排序是一个知名度极高的排序算法，其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。

算法描述

从数列中挑出一个元素，称为”基准”（pivot），
重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

算法实现

public void quickSort(int[] arr, int low, int high){
    if (low >= high){
        return;
    }
    int p = partition(arr, low, high);
    quickSort(arr, low, p);
    quickSort(arr, p+1, high);
}
public int partition(int[] arr, int low, int high){
    int pivot = arr[low]; //基准
    while (low < high){
        while (arr[high] >= pivot && low < high){
            high--;
        }
        arr[low] = arr[high];
        while (arr[low] < pivot && low < high){
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

稳定性

快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。

适用场景

快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。