排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。下面主要对一些常见的排序算法做介绍，并分析它们的时空复杂度。

排序汇总 排序算法性能比较

1. 选择排序

1.1 简单选择排序

简单选择排序的思想是：设排序序列的记录个数为n，进行n-1次大遍历，每次遍历i，找出（i到n中）的最小值并与i进行交换。

static void funSelectionSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int length = array.length;
        for(int start = 0; start < length; start++) {
            int minIndex = start;
            for (int i = start + 1; i < length; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
            }
            int temp = array[start];
            array[start] = array[minIndex];
            array[minIndex] = temp;
        }
    }

1.2 堆排序

堆排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。
如果把堆对应一个数组，假设一个堆的数组A，树的根为A[1]，i表示某一结点的下标，则父结点为PARENT(i)，左儿子LEFT[i]，右儿子RIGHT[i]的关系如下：

PARENT(i)
      return |_i/2_|
LEFT(i)
      return 2i
RIGHT(i)
      return 2i + 1

堆排序示例

我们可以很容易的定义堆排序的过程：

• 由输入的无序数组构造一个最大堆，作为初始的无序区
• 把堆顶元素（最大值）和堆尾元素互换
• 把堆（无序区）的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
• 重复步骤2，直到堆的尺寸为1

这里我思维的误区：

最大堆的的左树和右树之间没有大小的可比性，他们两个只是都比父节点小；所以再是用最大堆概念的时候，只有最大值是有意义的。这事是为什么每次循环都会把堆顶提出来调整出一个最大堆（类似最大堆的删除），重复。

    public class HeapSort {
        public void main(String[] args) {
            int arr[] = {5, 6, 1, 0, 2, 9};
            heapsort(arr, 6);
            System.out.println(Arrays.toString(arr));
        }

        /***
         * 创建最大堆
         * @param a
         * @param len
         */
        void buildHeap(int a[], int len) {
            for (int i = len / 2 - 1; i >= 0; i--) {
                heapfy(a, i, len);
            }
        }

        /***
         * 对某一子树进行最大堆判断&调整
         * @param a
         * @param index 子树根节点index
         * @param heapsize 最大堆元素数
         */
        void heapfy(int a[], int index, int heapsize) {
            int left = index * 2 + 1;
            int right = left + 1;
            if (right < heapsize && a[right] > a[left]) {
                left = right;
            }
            if (a[index] < a[right]) {
                swap(a, index, left);
                heapfy(a, left, heapsize);
            }
        }

        /***
         * 最大堆排序
         * @param a
         * @param len
         */
        void heapsort(int a[], int len) {
            buildHeap(a, len);
            for (int i = len - 1; i >= 0; i--) {
                swap(a, i, 0);
                heapfy(a, 0, i);
            }
        }

        private void swap(int a[], int i, int j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

2. 交换排序

2.1 冒泡排序

冒泡排序的基本思想是：设排序序列的记录个数为n，进行n-1次遍历，每次遍历从开始位置依次往后比较前后相邻元素，这样较大的元素往后移，n-1次遍历结束后，序列有序。

例如，对序列(3,2,1,5)进行排序的过程是：共进行3次遍历，第1次遍历时先比较3和2，交换，继续比较3和1,交换，再比较3和5，不交换，这样第1次遍历结束，最大值5在最后的位置，得到序列(2,1,3,5)。第2次遍历时先比较2和1，交换，继续比较2和3，不交换，第2次遍历结束时次大值3在倒数第2的位置，得到序列(1,2,3,5)，第3次遍历时，先比较1和2，不交换，得到最终有序序列(1,2,3,5)。

需要注意的是，如果在某次遍历中没有发生交换，那么就不必进行下次遍历，因为序列已经有序。

    static void funBubbleSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int len = array.length;
        for (int i = 0; i < len - 1; i++) {
            boolean swap = false;
            for (int j = 0; j < len - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap = true;
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
            if (!swap) {
                return;
            }
        }
    }

2.2 快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

快速排序示意

快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：

• 从序列中挑出一个元素，作为"基准"(pivot).
• 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
• 对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

    class Quick {
        public void main() {
            int arr[] = {5, 6, 1, 0, 2, 9};
            quickSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }

        void quickSort(int[] array, int start, int end) {
            if (start >= end) {
                return;
            }
            int pivotIndex = partition(array, start, end);
            quickSort(array, start, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, end);
        }

        void swap(int[] array, int start, int end) {
            int tmp = array[start];
            array[start] = array[end];
            array[end] = tmp;
        }

        int partition(int[] array, int start, int end) {
            int pivot = array[end]; //选取最后一个元素作为比较基准
            int tail = start - 1;   //基准元素左侧元素index
            for (int i = start; i < end; i++) {
                if (array[i] <= pivot) {
                    swap(array, i, tail++);
                }
            }
            swap(array, tail + 1, end);
            return tail + 1;
        }
    }

3. 插入排序

3.1 直接插入排序

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果该元素（已排序）大于新元素，将该元素移到下一位置
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
• 将新元素插入到该位置后
• 重复步骤2~5

    void funDInsertSort(int[] array) {
        if (array == null) {
            return;
        }
        int len = array.length;
        for (int i = 1; i < len; i++) {
            int j = i;
            int tmp = array[i];
            while (j >= 1 && array[j - 1] > tmp) {
                array[j] = array[j - 1];
                j--;
            }
            array[j] = tmp;
        }
    }

3.2 shell排序|希尔排序

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

  
  希尔排序示例

    void shellSort(int[] array) {
        if (array == null) {
            return;
        }
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for (int i = gap; i < array.length; i++) {
                int j = i - gap;
                int tmp = array[i];
                while (j >= 0 && array[j] > tmp) {
                    array[j + gap] = array[j];
                    j -= gap;
                }
                array[j + gap] = tmp;
            }
        }
    }

4. 归并排序

归并排序是分治法的一个典型应用，它的主要思想是：将待排序序列分为两部分，对每部分递归地应用归并排序，在两部分都排好序后进行合并。
其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序，但是归并排序是一种稳定的排序算法，快速排序则不然。所谓稳定排序，表示对于具有相同值的多个元素，其间的先后顺序保持不变。对于基本数据类型而言，一个排序算法是否稳定，影响很小，但是对于结构体数组，稳定排序就十分重要。例如对于student结构体按照关键字score进行非降序排序：

    class MergeSort {
        public void main() {
            int arr[] = {5, 6, 1, 0, 2, 9};
            mergeSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }

        void mergeSort(int[] array, int start, int end) {
            if (start + 1 < end) {
                int len1 = (end - start) / 2;
                int len2 = end - start + 1 - len1;
                mergeSort(array, start, start + len1 - 1);
                mergeSort(array, start + len1, end);

                mergeArray(array, start, end);
            }
        }

        private void mergeArray(int[] array, int start, int end) {
            int len1 = (end - start) / 2;
            int len2 = end - start + 1 - len1;
            int i = 0;
            int j = 0;
            int[] result = new int[end - start + 1];
            while (i < len1 && j < len2) {
                if (array[start + i] <= array[start + len1 + j]) {
                    result[i + j] = array[start + i];
                    i++;
                } else {
                    result[i + j] = array[start + len1 + j];
                    j++;
                }
            }
            System.arraycopy(result, 0, array, start, len1 + len2);
        }
    }