注：本文僅僅對十種常見排序算法進行簡單地實現(xiàn)過程分析邓梅，以及代碼實現(xiàn)猜年。
補充：我們常常對固定容量的數(shù)組使用排序算法替饿，但是如果換成動態(tài)數(shù)組(ArrayList)或者是鏈表赞别，又怎樣對他們進行排序吶滤馍。第3部分主要講解對其他動態(tài)數(shù)組和鏈表中的元素如何使用排序算法岛琼。
1、排序算法的相關(guān)術(shù)語
穩(wěn)定性：如果a本來在b的前面纪蜒，且a==b衷恭，經(jīng)過排序后，a仍然在b的前面則說明排序算法是穩(wěn)定的纯续，反之是不穩(wěn)定的随珠。
內(nèi)排序：所有操作都在內(nèi)存中完成灭袁。
外排序：由于數(shù)據(jù)量太大，因此把數(shù)據(jù)放在磁盤中窗看，而排序只有通過內(nèi)存和磁盤的數(shù)據(jù)傳輸才能進行茸歧。
時間復(fù)雜度：執(zhí)行一個算法所需要的時間。
空間復(fù)雜度：執(zhí)行完一個程序所花費的內(nèi)存显沈。
2软瞎、常用的排序算法（以實現(xiàn)遞增排序為例）
2.1冒泡排序（穩(wěn)定）
從頭到尾依次比較相鄰的兩個元素，如果第一個元素比第二個大拉讯，則交換位置涤浇，則一輪比較之后，最大的元素位于最后面的位置魔慷。重復(fù)該步驟只锭，直到所有元素都排序完成。
//冒泡排序
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選擇排序（不穩(wěn)定）
首先在未排序序列中找到最小的元素院尔，存放到序列的起始位置蜻展，然后從剩下的未排序元素中繼續(xù)尋找最小的元素放到已排序序列的末尾，直到所有元素均排序完畢邀摆。
//選擇排序
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插入排序（穩(wěn)定）
構(gòu)建有序序列，將未排序的元素從右往左（從后往前）依次插入到有序序列中栋盹。從第一個元素開始就可以認為該元素是有序的施逾，然后取出下一個元素進行插入。(從數(shù)組無序部分依次取出一個元素插入到有序部分)
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希爾排序（不穩(wěn)定）
希爾排序也是一種插入排序音念，它是在簡單插入排序的基礎(chǔ)上進行改進后的一個更高效的版本，希爾排序的平均時間復(fù)雜度為O(nlogn)躏敢。
希爾排序的算法步驟為：先選擇一個增量gap闷愤，一般選擇gap=nums.length/2，該初始增量被稱為希爾增量件余。通過該增量可以將序列劃分成若干個子序列讥脐，每次對子序列進行簡單插入排序可以使得序列整體變得有序。每次將增量折半啼器，當增量為1時旬渠，需要對整個序列進行簡單插入排序，但由于整個序列已經(jīng)有一定的有序性端壳，因此不會有大規(guī)模的序列整體移動告丢，進而提高了簡單插入排序的性能。
public void shellSort(int[] nums){
//選擇希爾增量作為初始增量
int gap=nums.length/2;
//直到增量變?yōu)?為止
while(gap>0){
//對當前增量下的所有子序列進行簡單插入排序损谦，有多少個增量就有多少個子序列
for(int i=0;i<gap;i++){
//對其中一個子序列進行簡單插入排序
int j=i;//記錄有序部分最后一個元素的索引
int k=i+gap;//記錄無序部分第一個元素的索引
while(k<nums.length){//直到無序部分已經(jīng)沒有元素為止
//找到k位置的元素應(yīng)插入的位置,同時移出元素位置岖免，為插入操作做準備
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歸并排序（穩(wěn)定）
歸并排序采用分治策略岳颇，整個過程可以視作兩個階段，即分的階段與治的階段颅湘。分的階段就是將整個序列劃分成若干個有序的子序列（序列中元素個數(shù)為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部分的元素從原數(shù)組中復(fù)制到臨時數(shù)組中備用
for(int k=left;k<=right;k++){
temp[k]=nums[k];
}
//開始合并這兩個有序序列
for(int k=left;k<=right;k++){
//如果第一個序列中已經(jīng)遍歷完了，則直接添加第二個序列中的元素
if(i==mid+1){
nums[k]=temp[j++];
}
//如果第二個序列中已經(jīng)遍歷完了释移，則直接添加第一個序列中的元素
else if(j==right+1){
nums[k]=temp[i++];
}
//判斷哪一個序列中相應(yīng)位置的元素更小叭披，并將小的元素更新到nums中
else if(temp[i]<=temp[j]){//加上等于號可以保證算法的穩(wěn)定性
nums[k]=temp[i++];
}
else{
nums[k]=temp[j++];
}
}
}
2.6快速排序（非穩(wěn)定）
在待排序序列中隨機選擇一個基準點，將小于基準點的元素放到基準點前面玩讳，大于或等于的放到基準點后面，此時就找到了基準點應(yīng)該排列的位置嚼贡。然后在基準點左右兩邊的子序列中執(zhí)行同樣的操作熏纯，直到子序列中有序為止（元素個數(shù)為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有可能出現(xiàn)大于或等于right的情況樟澜，舉極端情況下的示例即可知道
//找到基準點，這里選擇序列最后一個元素作為基準點
int pivot=nums[right];
int i=left;
int j=right;
while(i<j){
//先從前往后叮盘，尋找比基準點大或等于的元素秩贰，找到之后進行交換位置
while(i<j&&nums[i]<pivot){//如果i==j則說明i到j(luò)-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堆排序（非穩(wěn)定）
學(xué)習(xí)堆排序之前必須知道堆這種數(shù)據(jù)結(jié)構(gòu)。堆是一棵完全二叉樹(完全二叉樹的層序遍歷結(jié)果就是數(shù)組順序遍歷的結(jié)果)柔吼，分為大頂堆和小頂堆毒费，大頂堆每個節(jié)點的值都大于或等于它左右子樹上節(jié)點的值，小頂堆每個節(jié)點的值都小于或等于它左右子樹上節(jié)點的值愈魏。
堆可以用數(shù)組實現(xiàn)觅玻，在數(shù)組arr中有以下關(guān)系：
大頂堆：arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2];
小頂堆：arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2];
堆排序的基本思想是（升序采用大頂堆，降序采用小頂堆）：將待排序序列構(gòu)造成一個大頂堆培漏，此時溪厘，整個序列的最大值就是堆頂元素，將其與末尾元素進行交換牌柄，則末尾元素就是最大值畸悬。然后，將剩余的n-1個元素重新構(gòu)造成大頂堆珊佣，再次將頂堆元素與索引n-1處的元素進行交換蹋宦。反復(fù)執(zhí)行披粟，直到堆里面的元素個數(shù)為1時，說明已經(jīng)排序完成了妆档。
//懶人方法
public void heapSort(int[] nums){
//將nums構(gòu)建成一個大頂堆
//利用優(yōu)先隊列創(chuàng)建一個大頂堆
PriorityQueue<Integer> heap=new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer num1,Integer num2){
return num2-num1;
}
});
//將數(shù)組元素放到大頂堆中
for(int n:nums){
heap.offer(n);
}
//每次將彈出的堆頂元素從后往前放到數(shù)組中僻爽；
for(int i=nums.length-1;i>=0;i--){
int temp=heap.poll();
nums[i]=temp;
}
}
若不借助額外的空間來實現(xiàn)堆排序，則需要先清楚堆是一棵完全二叉樹贾惦，而完全二叉樹的層序遍歷結(jié)果就是數(shù)組順序遍歷的結(jié)果胸梆。因此可以知道nums[nums.length-1]一定是最后一個葉子節(jié)點。
知道了最后一個葉子節(jié)點的索引值须板，則可以知道最后一個非葉子節(jié)點的索引值index碰镜。由完全二叉樹的數(shù)組實現(xiàn)性質(zhì)可知2*index+1=nums.length-1或者2*index+2=nums.length-1，則index=(nums.length/2)-1;
知道了最后一個非葉子節(jié)點的位置之后习瑰，將其與子節(jié)點比較大小后然后調(diào)整他們的相對位置绪颖。然后遍歷倒數(shù)第二個非葉子節(jié)點，再執(zhí)行同樣的操作甜奄。遍歷完所有的非葉子節(jié)點之后柠横，則堆構(gòu)建完成。
public void heapSort(int[] nums){
//得到最后一個非葉子節(jié)點的位置
int last=nums.length/2-1;
//循環(huán)調(diào)整非葉子節(jié)點與其子節(jié)點的相對順序
for(int i=last;i>=0;i--){
buildeHeap(nums,i);
}
//大頂堆構(gòu)造好后课兄，其頂堆元素位于序列第一位牍氛，將堆頂元素依次放到序列無序部分末尾。
for(int i=nums.length-1;i>=0;i--){
swap(nums,0,i);
adjustHeap(nums,0,i);
}
}
//構(gòu)造堆時的調(diào)整過程
public void buildeHeap(int nums,int i){
int temp=nums[2*i+1];//用于保存較大的葉子節(jié)點
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));
}
}
//堆建好后烟阐，交換堆頂元素之后的調(diào)整過程（使其重新變成大頂堆）
public void adjustHeap(int nums,int i,int j){
//從堆頂開始往下調(diào)整,i保存堆頂元素的位置搬俊，j保存最后一個葉子節(jié)點的位置
for(int k=2*i+1;k<=j;k=2*k+1){//k保存左子節(jié)點的位置，則右子節(jié)點的位置為k+1
//如果有右子節(jié)點蜒茄，且右子節(jié)點的元素比左子節(jié)點的大,則指向值較大的子節(jié)點
if(k+1<=j&&nums[k+1]>nums[k]){
k++;
}
//如果子節(jié)點的值比父節(jié)點大唉擂，則交換位置。
//由于第一次構(gòu)造大頂堆的時候檀葛，其節(jié)點的值都比子節(jié)點大玩祟，將堆頂元素替換掉后，只有堆頂元素不滿足大頂堆的性質(zhì)驻谆，因此應(yīng)該將堆頂元素往下移動到合適位置即可卵凑。
if(nums[i]<nums[k]){
swap(nums,i,k);
}
else{//找到了正確的位置就說明調(diào)整完成了
break;
}
//更新需要繼續(xù)調(diào)整的節(jié)點索引
i=k;
}
}
public void swap(int[] nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
由以上代碼可知，建堆是可以復(fù)用調(diào)整堆的代碼的胜臊，從而使得代碼更加簡化勺卢。
2.8計數(shù)排序（穩(wěn)定）
計數(shù)排序要求待排序序列中的元素都是整數(shù)，且在一定范圍內(nèi)象对。它通過創(chuàng)建一個額外數(shù)組黑忱，將待排序序列中元素出現(xiàn)次數(shù)存放到額外數(shù)組中以元素值為下標的位置，最后再遍歷該額外數(shù)組，依次取出元素即可甫煞。因此額外數(shù)組的大小為：max-min+1菇曲。
當輸入的元素是n 個0到k之間的整數(shù)時，它的運行時間是 O(n + k)抚吠。計數(shù)排序不是比較排序常潮，排序的速度快于任何比較排序算法。由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1）楷力，這使得計數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組喊式，需要大量時間和內(nèi)存。
public void countSort(int[] nums){
//1萧朝、找出數(shù)組中的最大值與最小值岔留，然后創(chuàng)建額外數(shù)組
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、將原數(shù)組中元素出現(xiàn)次數(shù)存放到額外數(shù)組中以（元素值減去最小值）為下標的位置
for(int n:nums){
extraArray[n-min]++;//int類型的默認值是0
}
//3检柬、將額外數(shù)組中計數(shù)不為0的索引值依次返回到原數(shù)組中献联，完成排序
int j=0;
for(int i=0;i<extraArray.length;i++){
while((extraArray[i]--)!=0){
nums[j++]=i+min;
}
}
}
2.9桶排序（穩(wěn)定）
桶排序和計數(shù)排序具有類似的算法思想，計數(shù)排序的局限性在于當序列中的數(shù)值相隔較遠時何址，也仍然要創(chuàng)建max-min+1容量的額外數(shù)組里逆，會造成大量的時間和空間浪費。
桶排序可以在一定程度上減輕這種浪費用爪，它將序列中的元素均勻分配到桶中（桶的數(shù)量是自定義的）运悲，然后對桶中的元素進行單獨排序，最后將每個桶中的元素組合到一起便構(gòu)成了總的排序序列项钮。
算法步驟為：
1、根據(jù)桶的數(shù)量bucketCount和（max-min+1）來分配桶內(nèi)的空間大小space=(max-min+1)/bucketCount
2希停、根據(jù)元素的值arr[i]與桶空間大小space烁巫，將待排序序列位置i處的元素放到第bucketIndex個桶內(nèi)梦碗，bucketIndex=Math.floor(arr[i]-min)/space
3风纠、對桶內(nèi)的元素進行排序，可以采用其他的排序算法肠牲，比如插入排序或者快速排序等违崇。
4阿弃、將非空桶內(nèi)的元素組合起來組成新的排序序列。
public void bucketSort(int[] nums,int bucketCount){
//1羞延、分配桶內(nèi)的空間大小
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中的元素分配到桶中；這里桶中的數(shù)據(jù)結(jié)構(gòu)采用鏈表
ArrayList<Integer>[] buckets=new ArrayList[bucketCount];
for(int i=0;i<nums.length;i++){
int index= (int) Math.floor((nums[i]-min)/space);//index為當前元素所應(yīng)在的桶的下標
if(buckets[index]==null||buckets[index].size()==0){//如果index桶中沒有元素則直接加入
buckets[index]=new ArrayList<>();
buckets[index].add(nums[i]);
}
else{//3伴箩、如果index桶中有元素則進行桶內(nèi)的插入排序
int j=buckets[index].size()-1;
while(j>=0&&buckets[index].get(j)>nums[i]){
if(j+1==buckets[index].size()){//鏈表中復(fù)制最后一個元素的方法
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基數(shù)排序（穩(wěn)定）
基數(shù)排序與桶排序的算法思想類似，基數(shù)排序中會固定設(shè)置10個桶，根據(jù)元素個位（或者十位棺蛛、百位等）上的數(shù)值將元素放到對應(yīng)的桶中怔蚌，若序列中元素的最大值是一個千位數(shù)，則將元素放到對應(yīng)桶中的過程應(yīng)該要執(zhí)行4次旁赊，依次為按個位放置桦踊、按十位放置、按百位放置终畅、按千位放置（這種從低位到高位的順序叫最低位優(yōu)先LSD）（若是想按照遞減的順序進行排序則需要先按照最高位進行放置其次是低位的順序進行放置籍胯，這種方式叫做**最高位優(yōu)先MSD**）。當執(zhí)行最后一次放置操作時声离，每個桶內(nèi)的元素都已經(jīng)是有序的了芒炼，再把每個桶中的元素組織起來就得到了最終的排序序列。
算法中需要用到的功能有：
得到序列中最大值的位數(shù)
得到元素個位术徊、十位本刽、百位等上的數(shù)值
//基數(shù)排序
public void radixSort(int[] nums){
int max=getMaxBit(nums);
//創(chuàng)建10個桶
ArrayList<Integer>[] radixBuckets=new ArrayList[10];
for(int count=0;count<max;count++) {
//遍歷序列將元素放到對應(yīng)的基數(shù)桶中
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]);
}
//遍歷每個基數(shù)桶，將基數(shù)桶中的元素依次放到nums數(shù)組中備用赠涮，并清空每個基數(shù)桶備用
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();//清空基數(shù)桶備用
}
}
}
}
//基數(shù)排序所用函數(shù)：得到序列中最大元素的位數(shù)子寓，以確定會執(zhí)行多少輪給桶分配元素的操作,即最高按哪一位進行分配元素
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有多少位數(shù)，k==0表示只有個位數(shù)
}
//基數(shù)排序所用函數(shù)：得到元素每一位上的值,以確定在某一輪中該元素分配到哪一個桶中,k表示輪數(shù)(k==0表示個位笋除，表示第一輪)
// 求桶的 index 的除數(shù)斜友，如：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;
}
注意：****上述基數(shù)排序的代碼僅僅只能完成對正整數(shù)進行排序，而不適合于含有負整數(shù)的序列垃它。對于具有負整數(shù)的序列要使用基數(shù)排序鲜屏，有一種簡單的方法就是將負數(shù)和正數(shù)分開之后再分別使用基數(shù)排序，當然了這種方法可能看起來會比較弱国拇，另一種方法是一次性創(chuàng)建19個桶洛史，分別對應(yīng)-9~9的數(shù)值。
注意：后三種排序都可以說是非比較性質(zhì)的排序酱吝，其中計數(shù)排序和基數(shù)排序只能實現(xiàn)整數(shù)排序也殖，而基于比較的桶排序（桶內(nèi)采用比較排序）是可以實現(xiàn)小數(shù)排序的。
3务热、其他數(shù)據(jù)結(jié)構(gòu)下的排序算法
3.1對動態(tài)數(shù)組進行插入排序
對于動態(tài)數(shù)組（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對鏈表進行插入排序
動態(tài)維護一個鏈表的有序部分捆毫，初始為只有一個節(jié)點的部分就是有序的。記錄有序部分的最后一個節(jié)點last该镣，從last節(jié)點之后的節(jié)點cur往后遍歷冻璃，若節(jié)點cur的值大于或等于last响谓，則說明cur也是有序的。否則省艳，就從有序部分的第一個節(jié)點往后找該節(jié)點應(yīng)該放置的位置娘纷，并將其插入進去。更新cur為last的下一個節(jié)點跋炕。
時間復(fù)雜度（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;
//創(chuàng)建一個前驅(qū)節(jié)點赖晶，方便在head前插入節(jié)點
ListNode dummy=new ListNode(0);
dummy.next=head;
//需要保存有序部分的最后一個節(jié)點
ListNode last=head;
//應(yīng)該是從head節(jié)點的下一個節(jié)點來遍歷
ListNode cur=head.next;
while(cur!=null){
//如果當前節(jié)點大于last節(jié)點的值則說明當前節(jié)點不需要移動位置
if(cur.val>=last.val){
last=cur;
}
//如果小于則移動該節(jié)點到相應(yīng)的位置
else{
//從dummy節(jié)點開始找該節(jié)點應(yīng)該位于的位置
ListNode temp=dummy;
while(temp.next.val<cur.val){
temp=temp.next;
}
//把cur斷開,并連接到相應(yīng)位置
last.next=cur.next;
ListNode t=temp.next;
temp.next=cur;
cur.next=t;
}
cur=last.next;
}
return dummy.next;
}
}
3.3對鏈表進行歸并排序
與對數(shù)組進行歸并排序的思想相同，不過在治的階段變成了合并兩個有序鏈表辐烂。代碼如下遏插。
/**
* 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);
}
//自頂向下歸并排序，時間復(fù)雜度為o(nlogn)纠修，空間復(fù)雜度為o(logn)
public ListNode sortList1(ListNode head,ListNode tail){
//向下劃分的終止條件為頭結(jié)點為null胳嘲，則返回null，或者該子序列中只有一個節(jié)點（head==tail）扣草，則將head指向null
if(head==null)return head;
if(head.next==tail){
head.next=null;
return head;
}
//采用快慢指針的方式獲取到鏈表的中間節(jié)點,便于繼續(xù)向下劃分
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;
//需要一個節(jié)點來保存有序部分的最后一個節(jié)點
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對鏈表進行快速排序
與對數(shù)組進行快速排序的思想相同了牛，也是找到一個基準節(jié)點，并將小于基準節(jié)點的節(jié)點移動到前面去辰妙，大于基準節(jié)點的節(jié)點移動到后面鹰祸，一輪下來就確定了基準節(jié)點所處的位置。由于是在鏈表中密浑，因此要采用雙指針方法蛙婴，分別記錄頭節(jié)點與尾結(jié)點。代碼如下所示尔破。
/**
* 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);
}
//使用快速排序方法對鏈表進行排序
//選擇頭節(jié)點作為基準值街图，從頭結(jié)點的下一個節(jié)點開始，將小于基準值的節(jié)點頭插到基準節(jié)點之前懒构，將大于基準節(jié)點的節(jié)點尾插到基準節(jié)點之后台夺，完成一輪partition操作。由于要頭插和尾插痴脾，因此需要設(shè)定兩個指針，分別用來保存頭插節(jié)點與尾插節(jié)點
public ListNode quickSort(ListNode head,ListNode end){
if(head==end||head.next==end)return head;
//ListNode p=head;//基準節(jié)點,每次都選擇鏈表的第一個節(jié)點
ListNode h=head;//頭插節(jié)點
ListNode t=head;//尾插節(jié)點
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;
}
}
