注：本文仅仅对十种常见排序算法进行简单地实现过程分析，以及代码实现。
补充：我们常常对固定容量的数组使用排序算法，但是如果换成动态数组(ArrayList)或者是链表，又怎样对他们进行排序呐。第3部分主要讲解对其他动态数组和链表中的元素如何使用排序算法。
1、排序算法的相关术语
稳定性：如果a本来在b的前面，且a==b，经过排序后，a仍然在b的前面则说明排序算法是稳定的，反之是不稳定的。
内排序：所有操作都在内存中完成。
外排序：由于数据量太大，因此把数据放在磁盘中，而排序只有通过内存和磁盘的数据传输才能进行。
时间复杂度：执行一个算法所需要的时间。
空间复杂度：执行完一个程序所花费的内存。
2、常用的排序算法（以实现递增排序为例）
2.1冒泡排序（稳定）
从头到尾依次比较相邻的两个元素，如果第一个元素比第二个大，则交换位置，则一轮比较之后，最大的元素位于最后面的位置。重复该步骤，直到所有元素都排序完成。
//冒泡排序
public void bubbleSort(int[] nums){
for(int i=0;i<nums.length;i++){
for(int j=1;j<nums.length-i;j++){
//相邻的两个元素依次进行比较交换
if(nums[j-1]>nums[j]){
int temp=nums[j-1];
nums[j-1]=nums[j];
nums[j]=temp;
}
}
}
}
2.2选择排序（不稳定）
首先在未排序序列中找到最小的元素，存放到序列的起始位置，然后从剩下的未排序元素中继续寻找最小的元素放到已排序序列的末尾，直到所有元素均排序完毕。
//选择排序
public void selectSort(int[] nums){
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
//将i位置处的元素与后面的元素逐个比较，选出最小的值再填充到i位置
if(nums[j]<nums[i]){
int temp=nums[j];
nums[j]=nums[i];
nums[i]=temp;
}
}
}
}
2.3插入排序（稳定）
构建有序序列，将未排序的元素从右往左（从后往前）依次插入到有序序列中。从第一个元素开始就可以认为该元素是有序的，然后取出下一个元素进行插入。(从数组无序部分依次取出一个元素插入到有序部分)
public void insertSort(int[] nums){
//需要一个指针指示有序部分最后一个元素的索引,初始化为0
int j=0;
for(int i=1;i<nums.length;i++){
需要一个指针指示无序部分第一个元素的位置，方便将有序部分插入位置之后的元素进行后移
int x=i;
int numsi=nums[i];//先保存i位置处的值
//将numsi插入到正确位置
while(j>=0&&nums[j]>numsi){
nums[x]=nums[--x];//给插入元素腾出空间,后移元素
j--;
}
nums[j+1]=numsi;
//更新有序部分最后一个元素的索引
j=i;
}
}
2.4希尔排序（不稳定）
希尔排序也是一种插入排序，它是在简单插入排序的基础上进行改进后的一个更高效的版本，希尔排序的平均时间复杂度为O(nlogn)。
希尔排序的算法步骤为：先选择一个增量gap，一般选择gap=nums.length/2，该初始增量被称为希尔增量。通过该增量可以将序列划分成若干个子序列，每次对子序列进行简单插入排序可以使得序列整体变得有序。每次将增量折半，当增量为1时，需要对整个序列进行简单插入排序，但由于整个序列已经有一定的有序性，因此不会有大规模的序列整体移动，进而提高了简单插入排序的性能。
public void shellSort(int[] nums){
//选择希尔增量作为初始增量
int gap=nums.length/2;
//直到增量变为0为止
while(gap>0){
//对当前增量下的所有子序列进行简单插入排序，有多少个增量就有多少个子序列
for(int i=0;i<gap;i++){
//对其中一个子序列进行简单插入排序
int j=i;//记录有序部分最后一个元素的索引
int k=i+gap;//记录无序部分第一个元素的索引
while(k<nums.length){//直到无序部分已经没有元素为止
//找到k位置的元素应插入的位置,同时移出元素位置，为插入操作做准备
int numsk=nums[k];
while(j>=0&&nums[j]>numsk){
nums[j+gap]=nums[j];
j-=gap;
}
nums[j+gap]=numsk;
j=k;//更新有序部分最后一个元素的索引
k+=gap;//更新无序部分第一个元素的索引
}
}
gap/=2;
}
}
2.5归并排序（稳定）
归并排序采用分治策略，整个过程可以视作两个阶段，即分的阶段与治的阶段。分的阶段就是将整个序列划分成若干个有序的子序列（序列中元素个数为1时即有序）。治的阶段就是，将两个有序子序列合并成一个有序序列的过程，直到整个序列排序完成，则治的阶段完成。
public void mergeSort(int[] nums){
merge(nums,0,nums.length-1,new int[nums.length]);
}
public void merge(int[] nums,int left,int right,int[] temp){
//分的阶段，采用递归划分
if(left==right)return;
int mid=left+(right-left)/2;
merge(nums,left,mid,temp);
merge(nums,mid+1,right,temp);
//治的阶段，将两个有序序列合并成一个有序序列
int i=left;//记录第一个有序序列的第一个元素的起始位置
int j=mid+1;//记录第二个有序序列的第一个元素的起始位置
//先将left到right部分的元素从原数组中复制到临时数组中备用
for(int k=left;k<=right;k++){
temp[k]=nums[k];
}
//开始合并这两个有序序列
for(int k=left;k<=right;k++){
//如果第一个序列中已经遍历完了，则直接添加第二个序列中的元素
if(i==mid+1){
nums[k]=temp[j++];
}
//如果第二个序列中已经遍历完了，则直接添加第一个序列中的元素
else if(j==right+1){
nums[k]=temp[i++];
}
//判断哪一个序列中相应位置的元素更小，并将小的元素更新到nums中
else if(temp[i]<=temp[j]){//加上等于号可以保证算法的稳定性
nums[k]=temp[i++];
}
else{
nums[k]=temp[j++];
}
}
}
2.6快速排序（非稳定）
在待排序序列中随机选择一个基准点，将小于基准点的元素放到基准点前面，大于或等于的放到基准点后面，此时就找到了基准点应该排列的位置。然后在基准点左右两边的子序列中执行同样的操作，直到子序列中有序为止（元素个数为1）。
public void quickSort(int[] nums){
partition(nums,0,nums.length-1);
}
public void partition(int[] nums,int left,int right){
if(left>=right)return;//必须写成大于等于，因为left有可能出现大于或等于right的情况，举极端情况下的示例即可知道
//找到基准点，这里选择序列最后一个元素作为基准点
int pivot=nums[right];
int i=left;
int j=right;
while(i<j){
//先从前往后，寻找比基准点大或等于的元素，找到之后进行交换位置
while(i<j&&nums[i]<pivot){//如果i==j则说明i到j-1都没有大于或等于基准值的元素
i++;
}
if(i<j)nums[j--]=nums[i];//只有找到了满足条件的元素才更新值
while(i<j&&nums[j]>=pivot){
j--;
}
if(i<j)nums[i++]=nums[j];
}
nums[i]=pivot;
partition(nums,left,i-1);
partition(nums,i+1,right);
}
2.7堆排序（非稳定）
学习堆排序之前必须知道堆这种数据结构。堆是一棵完全二叉树(完全二叉树的层序遍历结果就是数组顺序遍历的结果)，分为大顶堆和小顶堆，大顶堆每个节点的值都大于或等于它左右子树上节点的值，小顶堆每个节点的值都小于或等于它左右子树上节点的值。
堆可以用数组实现，在数组arr中有以下关系：
大顶堆：arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2];
小顶堆：arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2];
堆排序的基本思想是（升序采用大顶堆，降序采用小顶堆）：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶元素，将其与末尾元素进行交换，则末尾元素就是最大值。然后，将剩余的n-1个元素重新构造成大顶堆，再次将顶堆元素与索引n-1处的元素进行交换。反复执行，直到堆里面的元素个数为1时，说明已经排序完成了。
//懒人方法
public void heapSort(int[] nums){
//将nums构建成一个大顶堆
//利用优先队列创建一个大顶堆
PriorityQueue<Integer> heap=new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer num1,Integer num2){
return num2-num1;
}
});
//将数组元素放到大顶堆中
for(int n:nums){
heap.offer(n);
}
//每次将弹出的堆顶元素从后往前放到数组中；
for(int i=nums.length-1;i>=0;i--){
int temp=heap.poll();
nums[i]=temp;
}
}
若不借助额外的空间来实现堆排序，则需要先清楚堆是一棵完全二叉树，而完全二叉树的层序遍历结果就是数组顺序遍历的结果。因此可以知道nums[nums.length-1]一定是最后一个叶子节点。
知道了最后一个叶子节点的索引值，则可以知道最后一个非叶子节点的索引值index。由完全二叉树的数组实现性质可知2*index+1=nums.length-1或者2*index+2=nums.length-1，则index=(nums.length/2)-1;
知道了最后一个非叶子节点的位置之后，将其与子节点比较大小后然后调整他们的相对位置。然后遍历倒数第二个非叶子节点，再执行同样的操作。遍历完所有的非叶子节点之后，则堆构建完成。
public void heapSort(int[] nums){
//得到最后一个非叶子节点的位置
int last=nums.length/2-1;
//循环调整非叶子节点与其子节点的相对顺序
for(int i=last;i>=0;i--){
buildeHeap(nums,i);
}
//大顶堆构造好后，其顶堆元素位于序列第一位，将堆顶元素依次放到序列无序部分末尾。
for(int i=nums.length-1;i>=0;i--){
swap(nums,0,i);
adjustHeap(nums,0,i);
}
}
//构造堆时的调整过程
public void buildeHeap(int nums,int i){
int temp=nums[2*i+1];//用于保存较大的叶子节点
if(2*i+2<nums.length&&nums[2*i+1]<nums[2*i+2]){
temp=nums[2*i+2];
}
if(nums[i]<temp){
swap(nums,i,temp==nums[2*i+1]?(2*i+1):(2*i+2));
}
}
//堆建好后，交换堆顶元素之后的调整过程（使其重新变成大顶堆）
public void adjustHeap(int nums,int i,int j){
//从堆顶开始往下调整,i保存堆顶元素的位置，j保存最后一个叶子节点的位置
for(int k=2*i+1;k<=j;k=2*k+1){//k保存左子节点的位置，则右子节点的位置为k+1
//如果有右子节点，且右子节点的元素比左子节点的大,则指向值较大的子节点
if(k+1<=j&&nums[k+1]>nums[k]){
k++;
}
//如果子节点的值比父节点大，则交换位置。
//由于第一次构造大顶堆的时候，其节点的值都比子节点大，将堆顶元素替换掉后，只有堆顶元素不满足大顶堆的性质，因此应该将堆顶元素往下移动到合适位置即可。
if(nums[i]<nums[k]){
swap(nums,i,k);
}
else{//找到了正确的位置就说明调整完成了
break;
}
//更新需要继续调整的节点索引
i=k;
}
}
public void swap(int[] nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
由以上代码可知，建堆是可以复用调整堆的代码的，从而使得代码更加简化。
2.8计数排序（稳定）
计数排序要求待排序序列中的元素都是整数，且在一定范围内。它通过创建一个额外数组，将待排序序列中元素出现次数存放到额外数组中以元素值为下标的位置，最后再遍历该额外数组，依次取出元素即可。因此额外数组的大小为：max-min+1。
当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
public void countSort(int[] nums){
//1、找出数组中的最大值与最小值，然后创建额外数组
int max=Integer.MIN_VALUE;
int min=Integer.MAX_VALUE;
for(int n:nums){
if(max<n)max=n;
if(min>n)min=n;
}
int extraArray=new int[max-min+1];
//2、将原数组中元素出现次数存放到额外数组中以（元素值减去最小值）为下标的位置
for(int n:nums){
extraArray[n-min]++;//int类型的默认值是0
}
//3、将额外数组中计数不为0的索引值依次返回到原数组中，完成排序
int j=0;
for(int i=0;i<extraArray.length;i++){
while((extraArray[i]--)!=0){
nums[j++]=i+min;
}
}
}
2.9桶排序（稳定）
桶排序和计数排序具有类似的算法思想，计数排序的局限性在于当序列中的数值相隔较远时，也仍然要创建max-min+1容量的额外数组，会造成大量的时间和空间浪费。
桶排序可以在一定程度上减轻这种浪费，它将序列中的元素均匀分配到桶中（桶的数量是自定义的），然后对桶中的元素进行单独排序，最后将每个桶中的元素组合到一起便构成了总的排序序列。
算法步骤为：
1、根据桶的数量bucketCount和（max-min+1）来分配桶内的空间大小space=(max-min+1)/bucketCount
2、根据元素的值arr[i]与桶空间大小space，将待排序序列位置i处的元素放到第bucketIndex个桶内，bucketIndex=Math.floor(arr[i]-min)/space
3、对桶内的元素进行排序，可以采用其他的排序算法，比如插入排序或者快速排序等。
4、将非空桶内的元素组合起来组成新的排序序列。
public void bucketSort(int[] nums,int bucketCount){
//1、分配桶内的空间大小
int max=Integer.MIN_VALUE;
int min=Integer.MAX_VALUE;
for(int n:nums){
max= Math.max(n, max);
min= Math.min(n, min);
}
double space=(double) (max-min+1)/(double) bucketCount;
//2、将nums中的元素分配到桶中；这里桶中的数据结构采用链表
ArrayList<Integer>[] buckets=new ArrayList[bucketCount];
for(int i=0;i<nums.length;i++){
int index= (int) Math.floor((nums[i]-min)/space);//index为当前元素所应在的桶的下标
if(buckets[index]==null||buckets[index].size()==0){//如果index桶中没有元素则直接加入
buckets[index]=new ArrayList<>();
buckets[index].add(nums[i]);
}
else{//3、如果index桶中有元素则进行桶内的插入排序
int j=buckets[index].size()-1;
while(j>=0&&buckets[index].get(j)>nums[i]){
if(j+1==buckets[index].size()){//链表中复制最后一个元素的方法
buckets[index].add(buckets[index].get(j));
}
else{
buckets[index].set(j+1,buckets[index].get(j));
}
j--;
}
if(j+1==buckets[index].size())buckets[index].add(nums[i]);
else buckets[index].set(j+1,nums[i]);
}
}
//4、将各非空桶中的元素组合起来
int k=0;
for(int i=0;i<bucketCount;i++){
if(buckets[i].size()!=0){
for(int n:buckets[i]){//ArrayList是顺序遍历
nums[k]=n;
k++;
}
}
}
}
2.10基数排序（稳定）
基数排序与桶排序的算法思想类似，基数排序中会固定设置10个桶，根据元素个位（或者十位、百位等）上的数值将元素放到对应的桶中，若序列中元素的最大值是一个千位数，则将元素放到对应桶中的过程应该要执行4次，依次为按个位放置、按十位放置、按百位放置、按千位放置（这种从低位到高位的顺序叫最低位优先LSD）（若是想按照递减的顺序进行排序则需要先按照最高位进行放置其次是低位的顺序进行放置，这种方式叫做**最高位优先MSD**）。当执行最后一次放置操作时，每个桶内的元素都已经是有序的了，再把每个桶中的元素组织起来就得到了最终的排序序列。
算法中需要用到的功能有：
得到序列中最大值的位数
得到元素个位、十位、百位等上的数值
//基数排序
public void radixSort(int[] nums){
int max=getMaxBit(nums);
//创建10个桶
ArrayList<Integer>[] radixBuckets=new ArrayList[10];
for(int count=0;count<max;count++) {
//遍历序列将元素放到对应的基数桶中
for (int i = 0; i < nums.length; i++) {
int index = getNumber(nums[i], count);
if (radixBuckets[index] == null) radixBuckets[index] = new ArrayList<>();
radixBuckets[index].add(nums[i]);
}
//遍历每个基数桶，将基数桶中的元素依次放到nums数组中备用，并清空每个基数桶备用
int j = 0;
for (int i = 0; i < 10; i++) {
if (radixBuckets[i] != null) {
for (int n : radixBuckets[i]) {
nums[j] = n;
j++;
}
radixBuckets[i].clear();//清空基数桶备用
}
}
}
}
//基数排序所用函数：得到序列中最大元素的位数，以确定会执行多少轮给桶分配元素的操作,即最高按哪一位进行分配元素
public int getMaxBit(int[] nums){
int max=Integer.MIN_VALUE;
for(int n:nums){
max=Math.max(n,max);
}
int k=0;
while(max!=0){
max/=10;
k++;
}
return k;//k+1表示max有多少位数，k==0表示只有个位数
}
//基数排序所用函数：得到元素每一位上的值,以确定在某一轮中该元素分配到哪一个桶中,k表示轮数(k==0表示个位，表示第一轮)
// 求桶的 index 的除数，如：798
// 个位桶 index = (798 / 1) % 10 = 8
// 十位桶 index = (798 / 10) % 10 = 9
// 百位桶 index = (798 / 100) % 10 = 7
public int getNumber(int num,int k){
int temp=1;
while(k>0){
temp*=10;
k--;
}
return (num/temp)%10;
}
注意：****上述基数排序的代码仅仅只能完成对正整数进行排序，而不适合于含有负整数的序列。对于具有负整数的序列要使用基数排序，有一种简单的方法就是将负数和正数分开之后再分别使用基数排序，当然了这种方法可能看起来会比较弱，另一种方法是一次性创建19个桶，分别对应-9~9的数值。
注意：后三种排序都可以说是非比较性质的排序，其中计数排序和基数排序只能实现整数排序，而基于比较的桶排序（桶内采用比较排序）是可以实现小数排序的。
3、其他数据结构下的排序算法
3.1对动态数组进行插入排序
对于动态数组（ArrayList，Vector等）怎么进行插入排序呐？这里就要用到了基于二分查找的插入排序算法了。
ArrayList<Integer> list=new ArrayList<>();
//每插入一个元素就进行一次排序
public void Insert(Integer num) {
//基于二分查找的插入排序方法
int left=0;
int right=list.size()-1;
while(left<right){
int mid=left+(right-left)/2;
if(list.get(mid)<num){
left=mid+1;
}
else if(list.get(mid)>=num){
right=mid;
}
}
list.add(left,num);
}
3.2对链表进行插入排序
动态维护一个链表的有序部分，初始为只有一个节点的部分就是有序的。记录有序部分的最后一个节点last，从last节点之后的节点cur往后遍历，若节点cur的值大于或等于last，则说明cur也是有序的。否则，就从有序部分的第一个节点往后找该节点应该放置的位置，并将其插入进去。更新cur为last的下一个节点。
时间复杂度（O(n^2)）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
//使用插入排序的方式
public ListNode insertionSortList(ListNode head) {
if(head==null)return head;
//创建一个前驱节点，方便在head前插入节点
ListNode dummy=new ListNode(0);
dummy.next=head;
//需要保存有序部分的最后一个节点
ListNode last=head;
//应该是从head节点的下一个节点来遍历
ListNode cur=head.next;
while(cur!=null){
//如果当前节点大于last节点的值则说明当前节点不需要移动位置
if(cur.val>=last.val){
last=cur;
}
//如果小于则移动该节点到相应的位置
else{
//从dummy节点开始找该节点应该位于的位置
ListNode temp=dummy;
while(temp.next.val<cur.val){
temp=temp.next;
}
//把cur断开,并连接到相应位置
last.next=cur.next;
ListNode t=temp.next;
temp.next=cur;
cur.next=t;
}
cur=last.next;
}
return dummy.next;
}
}
3.3对链表进行归并排序
与对数组进行归并排序的思想相同，不过在治的阶段变成了合并两个有序链表。代码如下。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return sortList1(head,null);
}
//自顶向下归并排序，时间复杂度为o(nlogn)，空间复杂度为o(logn)
public ListNode sortList1(ListNode head,ListNode tail){
//向下划分的终止条件为头结点为null，则返回null，或者该子序列中只有一个节点（head==tail），则将head指向null
if(head==null)return head;
if(head.next==tail){
head.next=null;
return head;
}
//采用快慢指针的方式获取到链表的中间节点,便于继续向下划分
ListNode slow=head;
ListNode fast=head;
while(fast!=tail&&fast.next!=tail){
slow=slow.next;
fast=fast.next.next;
}
ListNode mid=slow;
ListNode node1=sortList1(head,mid);
ListNode node2=sortList1(mid,tail);
//划分好后采用合并两个有序链表的方式进行排序
return merge(node1,node2);
}
//合并两个有序链表
public ListNode merge(ListNode node1,ListNode node2){
ListNode dummy=new ListNode(0);
dummy.next=node1;
//需要一个节点来保存有序部分的最后一个节点
ListNode cur=dummy;
while(node1!=null||node2!=null){
if(node1==null){
cur.next=node2;
break;
}
if(node2==null){
cur.next=node1;
break;
}
if(node1.val<node2.val){
cur.next=node1;
node1=node1.next;
}
else{
cur.next=node2;
node2=node2.next;
}
cur=cur.next;
}
return dummy.next;
}
}
3.4对链表进行快速排序
与对数组进行快速排序的思想相同，也是找到一个基准节点，并将小于基准节点的节点移动到前面去，大于基准节点的节点移动到后面，一轮下来就确定了基准节点所处的位置。由于是在链表中，因此要采用双指针方法，分别记录头节点与尾结点。代码如下所示。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return quickSort(head,null);
}
//使用快速排序方法对链表进行排序
//选择头节点作为基准值，从头结点的下一个节点开始，将小于基准值的节点头插到基准节点之前，将大于基准节点的节点尾插到基准节点之后，完成一轮partition操作。由于要头插和尾插，因此需要设定两个指针，分别用来保存头插节点与尾插节点
public ListNode quickSort(ListNode head,ListNode end){
if(head==end||head.next==end)return head;
//ListNode p=head;//基准节点,每次都选择链表的第一个节点
ListNode h=head;//头插节点
ListNode t=head;//尾插节点
ListNode cur=head.next;
while(cur!=end){
ListNode temp=cur.next;
//头插
if(cur.val<head.val){
cur.next=h;
h=cur;
}
else{
t.next=cur;
t=cur;
}
cur=temp;
}
t.next=end;
ListNode node=quickSort(h,head);
head.next=quickSort(head.next,end);
return node;
}
}
