本文共 11437 字，大约阅读时间需要 38 分钟。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

各个算法的比较：

算法一、直接插入排序

直接插入排序的思想是每次将一个待排序的记录按照关键字大小的顺序插入到前面已经排好序的子序列中，直到全部记录插入完成,下面是一个排序的示例。

直接插入排序的代码： 第一种写法：

public void insertSort(int[] array) {           int len = array.length;        //i代表待插入元素，j代表有序子数列中的元素        int i,j;        //待插入元素从第二个元素开始        for( i = 1; i < len; i++) {           //待插入的元素            int num = array[i];            j = i;            //注意这里的判断条件，j > 0,与下面的代码进行对比学习            while(j > 0 && array[j-1] > num) {                   array[j] = array[j-1];                j--;            }            //当while循环结束时，j-1的位置第一个小于等于num的，所以num的位置应该在j            array[j] = num;        }    }

第二种写法：

public void insertSort(int[] array) {        int len = array.length;     int i,j;     for( i = 1; i < len; i++) {            int num = array[i];         j = i-1;         while(j >= 0 && array[j] > num) {                array[j+1] = array[j];             j--;         }         array[j+1] = num;     } }

效率分析：

空间复杂度：只用到常数个空间，因此为o(1)。 时间复杂度：最好的情况下，数组有序，此时每插入一个只需要比较一次，故时间复杂度为o(n)，但是在最坏的情况下，即数组逆序的情况下，总共需要比较(1+2+3+…+n-1) = (n*(n-1)/2)次，n代表元素个数，故时间复杂度为o(n²), 平均时间复杂度为o(n²)，由于其没有改变相同元素的相对顺序，所以它是一个稳定的排序算法,同时它适用于顺序存储和链式存储，当为链式存储时，我们需要从链表头部开始比较，直到遇到一个比待插入元素大的元素，然后插入到这个元素的位置，为了操作方便，我们重新创建一个链表用于存储有序子序列。

算法二、折半插入排序

折半插入排序的思想和直接插入排序的思想一样，只不过在查找待插入元素的位置时使用折半查找，这个算法相较直接插入排序算法，元素的比较次数减少，但是元素的移动次数并没有变，下面给出它的代码：

public void insertSort(int[] array) {           int len = array.length;        int i,j;        for( i = 1; i < len; i++) {               int num = array[i];            //找出待插入元素的插入位置           int position = binarySearch(array,num,0,i-1);           //移动元素，注意这里是从后往前移动           for(j = i-1; j >= position; j--) {                  array[j+1] = array[j];           }           array[position] = num;        }    }    //二分查找待插入的位置    public int binarySearch(int[] array,int target,int begin,int end) {           while(begin <= end) {               int mid = (begin+end)/2;            if(array[mid] > target) {                   end = mid-1;            } else {                   begin = mid + 1;            }        }        return begin;    }

空间复杂度为o(1),虽然比较次数减少，但是移动元素的次数没有减少，最坏的情况下（逆序）需要移动元素的次数为(1+2+…+n-1) = (n-1)*n/2,故时间复杂度仍为o(n²),但是这种排序算法只适用于顺序存储，不适用于链式存储，是稳定的排序算法。

算法三、希尔排序

代码如下：

public static void shellSort(int[] array) {           int len = array.length;        //增量k        int k = len/2;        //        for( k = len/2; k >= 1; k = k/2) {                           //直接插入排序的算法，只不过步长不一样            for(int i = k; i < len; i++) {                   int num = array[i];                int j = i-k;                while(j >= 0 && array[j] > num) {                       array[j+k] = array[j];                    j = j - k;                }                array[j+k] = num;            }        }    }

空间复杂度：用到常数个额外空间，复杂度为o(1)。

空间复杂度：由于希尔排序的时间复杂度依赖增量序列的函数，当n在某个特定值时，希尔排序的时间复杂度约为o(n^1.3),最坏情况下时间复杂度为o(n²)。 稳定性：当相同值在不同的组时，可能会造成相同值的相对顺序发生改变，所以其不是一个稳定的排序算法，如上述示例中49的相对顺序就发生了变化。

算法四、冒泡排序

冒泡排序的思想是从后往前（或者从前往后）两两比较相邻的元素，如果为逆序，即A[i-1]>A[i],则交换他们，直到序列比较完，此时为一趟冒泡排序，其结果就是把最小的元素交换到第一个位置（或者把最大的元素交换到最后的位置），每一趟冒泡排序完成就会有一个元素到其正确的位置上，因此，如果序列的元素个数为n,我们只需要(n-1)趟冒泡排序就可以完成整个序列的排序,下面是其从前往后排序的一个动图：

代码：

public void bubbleSort(int[] array) {           int len = array.length;        for(int i = len-1; i > 0; i--) {               //从前往后来两两比较，一趟排序后会有一个最大值在其正确的位置上            for(int j = 1; j <= i; j++) {                   if(array[j-1] > array[j]) {                       int temp = array[j-1];                    array[j-1] = array[j];                    array[j] = temp;                }            }        }    }

空间复杂度：用到常数个额外空间，复杂度为o(1)。

时间复杂度：最好情况下，即元素为顺序时，时间复杂度为o(n)，在最坏的情况下，即逆序，时间复杂度为o(n²)，平均情况下为o(n²)。

算法五、快速排序

快速排序的基本思想是基于分治法，在待排序的序列A[0…n-1]中任取一个元素作为中枢值mid，然后通过一趟排序将待排序的序列划分成独立的两个子序列[0…k-1]和[k+1…n-1],使得[0…k-1]中的元素都小于mid,[k+1…n-1]中元素都大于等于mid,此时mid放在了其最终的位置上，然后在分别对这两个子序列进行快排。

代码：

public void quickSort(int[] array,int begin,int end) {           int left = begin;        int right = end;        //如果只有一个元素，不用排序        if(begin >= end) {               return;        }        int flag = array[begin];        while(begin < end) {               //从左往右找到大于等于flag的元素            if(array[begin] < flag) {                   begin++;                continue;            }            //从后往前找比flag小于等于flag元素            if(array[end] > flag) {                   end--;                continue;            }            int temp = array[begin];            array[begin] = array[end];            array[end] = temp;            //这一步是为了让区间范围一直缩小，防止array[begin] = array[end]时,程序陷入死循，环，例如排序[1,1,1,1]            if(array[begin] == flag) {               end = end - 1;            } else {               begin = begin + 1;            }        }        quickSort(array,left,begin-1);        quickSort(array,begin+1,right);    }

注意上面两个if判断的条件，这样判断的好处即是begin和end始终有一个指向mid值，当begin = end时，此时begin就是mid的最终位置，此外仔细体会一下continue的用处。

空间复杂度：最好的情况下o(log2(n)),最坏的情况下为o(n)。 时间复杂度：如果序列的初始时基本有序或者逆序，此时快速排序效率最低，为o(n²),如果mid能够基本把序列分成两个部分，效率最高，为o(nlogn),平均情况下为o(nlogn)。 稳定性：不稳定的排序算法，可以想到如果在右区间存在两个相同的小于mid的元素，那么交换后它们的相对顺序将发生变化。

算法六、简单选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下： 初始状态：无序区为R[1…n]，有序区为空； 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区； n-1趟结束，数组有序化了。 代码：

public void selectSort(int[] array) {           for(int i = 0; i < array.length-1; i++) {               int minIndex = i;            for(int j = i+1; j < array.length; j++) {                   if(array[j] < array[minIndex]) {                       minIndex = j;                }            }            int temp = array[minIndex];            array[minIndex] = array[i];            array[i] = temp;        }    }

空间复杂度：o(1)。

时间复杂度：o(n²)。 稳定性：算法不是稳定的算法，如[2,2,1]。

算法七、堆排序

接着我们来看选择排序中的另一种排序—堆排序，由上面的直接选择排序分析，我们知道，在n个键值中选出最小值，至少进行n-1次比较，然而继续在剩余的n-1个键值中选择出第二个小的值是否一定要进行n-2次比较呢？如果能利用钱n-1次比较所得信息，是否可以减少以后各次选中的次数比较呢？基本这个，我们来看堆排序，堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。我们来看堆排序到底是怎么排的呢？下面我们以小堆为例，如下图所示：

如上图所示的序列是6、5、3、1、8、7、2、4，我们首先将其构建成一个堆，通过构建我们发现这个时候的序列为8、6、7、4、5、3、2、1，接着，我们1和8进行比较，发现1小于8，所以交互位置，刨去8，这个时候的序列为1、6、7、4、5、3、2，发现7比1大，交互位置，1比3小，交互位置，构成的是一个大顶堆了，这个时候，只需要7跟二叉树的最后一个节点进行比较即可，刨去7，依次类推，小编这里用语言描述的不是很准确，没有立体感，很难进行想象，小伙伴可以仔细看上面的这个动态图是如何进行堆排序的。

大根堆代码：

public void headAdjust(int[] array,int k,int len) {           //这里加入这个判断是为了防止在输出最后一个结点后结束headAdjust(array,0,-1);        if(len < 0) {               return;        }        int i = k;        //int temp = array[k];        for( i = 2 * k + 1; i <= len; i = i * 2 + 1) {               //如果有左右子树,并且左子树值小于右子树,i指向右子树            if(i+1 <= len && array[i] < array[i+1]) {                   i++;            }            if(array[i] > array[k]) {                   //交换根结点与较大子结点的值                int temp =  array[k];                array[k] = array[i];                array[i] = temp;                k = i;            } else {   //如果根结点值大于左右子结点或者根节点没有左右子结点，那么不需要在向下调节                break;            }        }    }    public void buildBigTree(int[] array) {           //构建大根堆，从第一个非叶子结点从下至上，从右至左调整结构        for(int i=array.length/2-1;i>=0;i--){               headAdjust(array,i,array.length-1);        }        //输出结点值        for(int j=array.length-1;j>=0;j--){               System.out.print(array[0]+",");            //将最后一个结点值赋值到array[0]            array[0] = array[j];            //调整剩下的结点成为一个大根堆            headAdjust(array,0,j-1);        }    }

小根堆代码：

public void AdjustSmallTree(int[] array,int k,int len) {           if(len < 0) {               return;        }        for(int i = 2 * k + 1;i <= len; i++) {               //如果有左右子树,并且左子树值大于右子树,i指向右子树            if(i+1 <= len && array[i] > array[i+1]) {                   i++;            }            if(array[k] > array[i]) {                   int temp = array[k];                array[k] = array[i];                array[i] = temp;            } else {                   break;            }        }    }    public void buildBigTree(int[] array) {           //构建小根堆，从第一个非叶子结点从下至上，从右至左调整结构        for(int i=array.length/2-1;i>=0;i--){               AdjustSmallTree(array,i,array.length-1);        }        //输出结点值        for(int j=array.length-1;j>=0;j--){               System.out.print(array[0]+",");            //将最后一个结点值赋值到array[0]            array[0] = array[j];            //调整剩下的结点成为一个小根堆            AdjustSmallTree(array,0,j-1);        }    }

空间复杂度：o(1)。

时间复杂度：建堆时间为o(n),每次调整时间为o(h),故总时间为o(nlogn)。 稳定性：是不稳定的算法。如[1,2,2]。

算法八、二路归并排序

基本思想：归并的含义是将两个或者两个以上的有序序列进行合并，形成一个更大的有序子序列，对于一个序列，我们可以把其每一个元素单独看成一个有序的子序列，然后两两合并成一个大的有序子序列，之后继续两两合并直到成为一个有序的子序列。

示例：

代码：

//用于合并两个有序数组[beign,mid]和[mid+1,end]public void merge(int[] array,int begin,int mid,int end) {           int left = begin;        int right = mid + 1;        int [] temp = new int[end-begin+1];        int count = 0;        while(left <= mid && right <=end) {               if(array[left] <= array[right]) {                   temp[count++] = array[left++];            } else {                   temp[count++] = array[right++];            }        }        while (left <= mid) {               temp[count++] = array[left++];        }        while (right <= end) {               temp[count++] = array[right++];        }        count = 0;        for(int i = begin; i <= end; i++) {               array[i] = temp[count++];        }    }	//归并排序    public  void mergeSort(int[] array,int begin,int end) {           if(begin >= end) {               return;        }        int mid = (begin + end) / 2;        mergeSort(array,begin,mid);        mergeSort(array,mid+1,end);        merge(array,begin,mid,end);    }

空间复杂度：合并数组用到了额外的空间，为o(n)。

时间复杂度：每趟合并的时间复杂度为o(n）,共需要进行logn趟，即时间复杂度为o(nlogn)。 稳定性：稳定的排序算法。

算法九、基数排序

基本思想：

先找十个桶：0~9 第一轮按照元素的个位数排序 桶内分别按照元素的个位数，按照数组元素的顺序依次存放对应的桶中，然后按照桶的顺序依次收集所有元素 第二轮：然后按照元素十位的大小依次放入桶中，后按照桶的顺序依次收集所有元素，重复这个过程直到所有的位数都被分配和收集一次，最后一次收集的结果即是有序序列，具体可以看下面的示例：

代码：

public void RadixSort(int[] array) {           //分配十个桶        List
   
    
     > list = new ArrayList<>();        //初始化桶        for(int i = 0; i < 10; i++) {               list.add(new ArrayList<>());        }        //找出数组中的最大值        int max = Integer.MIN_VALUE;        for(int i = 0; i < array.length; i++) {               if(array[i] > max) {                   max = array[i];            }        }        //找出最大值的位数        int len = (max + "").length();        //用于统计分配次数        int count = 0;        while(count < len) {               //用于统计当前是按照哪一位进行分配            int t = 0;            for(int i = 0; i < array.length; i++) {               	//找出对应位的数字                int num = ((array[i] / (int)Math.pow(10,t)) % 10);                //添加元素                list.get(num).add(array[i]);            }            count++;            t++;            int m = 0;            //收集元素            for(List
     
       l: list) {                   for(Integer num : l) {                       array[m++] = num;                }                //清空对应的桶                l.clear();            }        }    }
     
    
   

空间复杂度：一趟排序需要辅助空间为r,即r个桶，每个桶最大深度为n（n是元素个数），即最大空间复杂度为o(r*n)。

时间复杂度：总共需要进行d次分配和收集（d是最大元素的位数），每次分配需要遍历所有元素，复杂度为o(n),一趟收集需要遍历r个桶，故一趟分配和收集的时间复杂度为o(n+r),故总时间复杂度为o(d(n+r))。 稳定性：是稳定的排序算法。