轉載請注明出處
作者：@ZJXin
說明：本文所寫的排序,默認按從小到大排序。由于本人水平有限，如有不正確的地方歡迎留言指出稚虎，謝謝侧蘸！
排序算法是面試中經(jīng)常會被問到的問題裁眯，甚至會要求手寫算法，本文對一些常用的排序算法做了總結讳癌。本文涉及的代碼全部都運行驗證過穿稳。(堆排序沒有給出代碼實現(xiàn))
排序算法分類
1. 直接插入排序
算法思想
每次將無序區(qū)的第一個記錄按關鍵字插入到有序區(qū)的合適位置。
算法實現(xiàn)步驟
- 取出無序區(qū)第一個元素晌坤，并將該值賦值給一個臨時變量
- 在已經(jīng)排序的元素序列中從后向前掃描
- 如果所取元素大于新元素逢艘，將該元素向后移動一個位置
- 重復步驟三，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置中
- 重復1~5
算法流程圖
直接插入排序
Java代碼實現(xiàn)
/**
* 直接插入排序算法
*
* @param nums 待排序數(shù)組
*/
public void insertSort(int []nums){
//數(shù)組長度
int length = nums.length;
//要插入的數(shù)
int insertNum;
for(int i=1;i<length;i++){//遍歷數(shù)組
int j = i-1;//已排好序的元素序列的最大下標
insertNum = nums[i];
while(j>=0 && nums[j]>insertNum){
//首先判斷j是否>=0,不然將可能產生數(shù)組溢出
//序列從后往前循環(huán)
//將大于insertNum的數(shù)往后挪一格
nums[j+1] = nums[j--];
}
//將需要插入的數(shù)放在插入的位置
nums[j+1] = insertNum;
}
}
算法分析
- 時間復雜度
- 最佳情況：O(n)
- 最壞情況：O(n^2)
- 平均時間復雜度：O(n^2)
- 空間復雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
- 改進：希爾排序(縮小增量排序)
2. 希爾排序（縮小增量排序）
算法思想
希爾排序是對直接插入排序的一種改進泡仗。希爾排序將整個待排序序列按增量dk劃分為m個子序列埋虹，不斷縮小增量dk，重復這一過程娩怎，直到dk減少到1搔课，對整個序列進行一次直接插入排序，因此截亦，希爾排序也被稱為縮小增量排序爬泥。
希爾排序與直接插入排序的不同之處在于，直接插入排序每次對相鄰記錄進行比較崩瓤，記錄只移動一個位置袍啡，而希爾排序每次對相隔較遠(即增量)的記錄進行比較，使得記錄移動時跨越多個記錄却桶，實現(xiàn)宏觀上的調整境输。當增量為1時，此時序列已基本有序颖系，可將前邊的各趟的調整看做最后一趟的預處理嗅剖。
算法實現(xiàn)步驟
- 選擇一個增量序列t1、t2嘁扼、t3...tk(其中tk=1)
- 按增量序列個數(shù)k信粮，對待排序序列進行k趟排序
- 每趟排序，根據(jù)相應的增量dk趁啸，進行插入排序
算法流程圖
希爾排序
Java代碼實現(xiàn)
/**
* 希爾排序(縮小增量排序)
* 不穩(wěn)定
*
* @param nums 待排序數(shù)組
*/
public void sheelSort(int []nums){
int dk = nums.length;
do{
//縮小增量
//此處縮小增量可以自己設置强缘，一般縮小當前的一半
dk = dk/2;
sheelInsert(nums, dk);//進行一次希爾排序
}while(dk>0);//當增量為1時停止
}
/**
* 希爾排序一趟排序
* 如果把增量設置為1，則是簡單的插入排序
*
* @param nums 待排序數(shù)組
* @param dk 增量
*/
public void sheelInsert(int []nums,int dk){
int length = nums.length;
int insertNum;//待插入的值
for(int i=dk;i<length;i++){
int j=i-dk;
insertNum = nums[i];
while(j>=0 && nums[j]>insertNum){
//同樣的不傅，應該先檢測j是否比0小旅掂，否則可能產生數(shù)組溢出
//向后移動dk位
nums[j+dk] = nums[j];
j = j-dk;
}
nums[j+dk] = insertNum;//把待插入的 值放到正確的位置
}
}
算法分析
- 時間復雜度
- 最佳情況:O(n)
- 最壞情況:O(n^2)
- 平均情況:O(nlogn)
- 空間復雜度:O(1)
- 穩(wěn)定性:不穩(wěn)定
3. 簡單選擇排序
算法思想
每趟在未排序的序列中找到最小的元素，存放到未排序序列的起始位置访娶。
算法實現(xiàn)步驟
- 首先在未排序序列中找到最小元素商虐，存放到排序序列的起始位置
- 再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到已排序序列的末尾。
- 重復上述步驟称龙，直到所有元素均排序完畢。
算法流程圖
簡單選擇排序
Java代碼實現(xiàn)
/**
* 簡單選擇排序
* 每一個循環(huán)后再交換戳晌，簡單選擇排序
*
* @param nums 待排序數(shù)組
*/
public void selsectSort(int []nums){
int length = nums.length;//數(shù)組長度鲫尊，將這個值提出來，提高速度
for(int i=0; i<length; i++){//循環(huán)次數(shù)
int key = nums[i];
int position = i;
for(int j=i+1;j<length;j++){//選出最小的值和位置
if(key>nums[j]){
key = nums[j];
position = j;
}
}
//交換位置
nums[position] = nums[i];
nums[i] = key;
}
}
算法分析
- 時間復雜度
- 最壞沦偎、最佳疫向、平均:O(n^2)
- 空間復雜度：O(1)
- 穩(wěn)定性:不穩(wěn)定
4. 堆排序
算法思想
堆排序是對簡單排序的優(yōu)化，利用大頂堆所有非葉子結點均不小于其左右孩子結點這一特性來排序豪嚎。
算法實現(xiàn)步驟
- 將待排序列建成一個大頂堆
- 將頂堆結點與隊尾結點交換位置搔驼，堆長度減1
- 調整剩余結點為堆
- 重復步驟2~3
算法流程圖
堆排序
算法分析
- 時間復雜度
- 最壞、最好侈询、平均：O(nlogn)
- 空間復雜度:O(1)
- 穩(wěn)定性：不穩(wěn)定
5. 冒泡排序
算法思想
冒泡排序每趟排序舌涨，對相鄰兩個元素進行比較，如果順序錯誤則交換過來扔字，每趟排序后囊嘉，都將把未排序序列的最大值放在最后邊。每趟排序革为，越小的元素會經(jīng)由交換扭粱，慢慢地"浮"到數(shù)列頂端，這也是該算法名字的由來震檩。
算法實現(xiàn)步驟
- 將序列中所有元素相鄰兩兩比較琢蛤，將最大的放在最后面。
- 將剩余序列中所有元素相鄰兩兩比較抛虏，將最大的放在最后面博其。
- 重復第二步，直到只剩下一個數(shù)嘉蕾。
算法流程圖
冒泡排序
Java代碼實現(xiàn)
/**
* 冒泡排序
*
* @param nums 待排序數(shù)組
*/
public void bubbleSort(int []nums){
int length = nums.length;
int temp;
for(int i=0; i<length; i++){
for(int j=0; j<length-i-1; j++){
if(nums[j]>nums[j+1]){
//交換相鄰兩個數(shù)
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}
算法分析
- 時間復雜度：
最佳贺奠、最壞、平均:O(n^2) - 空間復雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
算法改進
- 改進方案一
設置一標志性變量pos错忱，用于記錄每趟排序中最后一次進行交換的位置儡率。由于pos位置之后的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。
/**
* 冒泡排序改進版本一
* 通過設置標志位來減少遍歷次數(shù)
*
* @param nums
*/
public void betterBubbleSort1(int []nums){
int length = nums.length;
int i= length -1; //初始時,最后位置保持不變
while ( i> 0) {
int pos= 0; //每趟開始時,無記錄交換
for (int j = 0; j< i; j++){
if (nums[j]> nums[j+1]) {
pos= j; //記錄交換的位置
int tmp = nums[j];
nums[j]=nums[j+1];
nums[j+1]=tmp;
}
i= pos; //為下一趟排序作準備
}
}
}
- 改進方案二
若某一趟排序中未進行一次交換以清，則排序結束 儿普。
/**
* 冒泡排序改進版本二
*
* @param nums 待排序數(shù)組
*/
public void betterBubbleSort2(int[] nums ) {
int len = nums .length;
boolean flag = true;
while (flag) {
flag = false;
for (int i = 0; i < len - 1; i++) {
if (nums [i] > nums [i + 1]) {
int temp = nums [i + 1];
nums [i + 1] = nums [i];
nums [i] = temp;
flag = true;
}
}
len--;
}
}
6. 快速排序
算法思想
分治法。通過一趟排序將待排記錄分割成獨立的兩部分掷倔，其中一部分記錄的關鍵字均比另一部分的關鍵字小眉孩，然后在分別對這兩部分記錄進行排序。
算法實現(xiàn)步驟
- 從數(shù)列中挑出一個元素，稱為“基準”
- 重新排序數(shù)列浪汪，所有比基準小的元素放在基準前邊巴柿，所有比基準大的放在基準后邊，該基準最后處于數(shù)列中間位置死遭。
- 遞歸地把小于基準值元素和大于基準值元素的子序列快速排序
算法流程圖
快速排序
Java代碼實現(xiàn)
/**
* 快速排序
* 不穩(wěn)定
*
* @param nums 待排序數(shù)組
* @param left 開始位置
* @param right 結束位置
*/
public void quickSort(int []nums,int left,int right){
if(left<right){
int base = nums[left];//選定的基準
int low = left;
int high = right;
while(low<high){
while(low<high && nums[high]>base){
//先從后往前遍歷,直到數(shù)值比基準小
high--;
}
//把數(shù)值比基準小的放到基準左邊
nums[low] = nums[high];
while(low<high && nums[low]<base){
//從前往后遍歷广恢，直到數(shù)值比基準大
low++;
}
//把數(shù)值比基準大的放到基準右邊
nums[high] = nums[low];
}
//把基準放到準確位置去
nums[low] = base;
//用同樣的方法,遞歸調用基準左邊的數(shù)組以及右邊的數(shù)組
quickSort(nums, left, low-1);
quickSort(nums, low+1, right);
}
}
算法分析
- 時間復雜度
- 最佳情況：O(nlogn)
- 最壞情況：O(n^2)
- 平均復雜度:O(nlogn)
- 空間復雜度:O(nlogn)
- 穩(wěn)定性:不穩(wěn)定
7.歸并排序
算法思想
分治法。歸并排序將待排序列一分為二呀潭，并對每個子數(shù)組遞歸排序钉迷，然后再把這兩個排好序的子數(shù)組合并為一個有序的數(shù)組。
算法實現(xiàn)步驟
- 把長度為n的輸入序列分為兩個長度為n/2的子序列
- 對這兩個子序列分別采用歸并排序
- 將兩個排序好的子序列合并成一個最終的排序序列
算法流程圖
歸并排序
Java代碼實現(xiàn)
/**
* 歸并排序
* 穩(wěn)定的排序算法
*
* @param nums 待排序數(shù)組
* @param low 待排序數(shù)組的起點
* @param high 待排序數(shù)組的終點
*/
public static void mergeSort(int []nums,int low,int high){
//算出分割點,2-路歸并即數(shù)組的中點
int mid = (high+low)/2;
if(low<high){
//遞歸分割
mergeSort(nums, low, mid);
mergeSort(nums, mid+1, high);
//調用歸并方法,將分割的進行歸并
merge(nums, low, mid, high);
}
}
/**
* 一次2-路歸并
* 可以想象成將兩個鏈表钠署，按照升序的方法組合成一條鏈表
*
* @param nums 待排序數(shù)組
* @param low 歸并的最低位
* @param mid 歸并的中間位置
* @param high 歸并的最高位
*/
public static void merge(int []nums,int low,int mid,int high){
//新建數(shù)組糠聪，放置臨時數(shù)據(jù)
int []temp = new int[high-low+1];
int i = low,j=mid+1;
int k=0;
//把較小的數(shù)先移到新數(shù)組中去
while(i<=mid && j<=high){
//遍歷兩路數(shù)組,直到一路結束為止
if(nums[i]<nums[j]){
temp[k++] = nums[i++];
}else{
temp[k++] = nums[j++];
}
}
//把左邊那路剩余的數(shù)放入數(shù)組
while(i<=mid){
temp[k++] = nums[i++];
}
//把右邊那路剩余的數(shù)放入數(shù)組
while(j<=high){
temp[k++] = nums[j++];
}
//把新數(shù)組的值覆蓋nums數(shù)組
//新數(shù)組的長度有可能比nums數(shù)組短
for(int t=0;t<temp.length;t++){
nums[t+low] = temp[t];
}
}
算法分析
- 時間復雜度
- 最佳、最壞谐鼎、平均:O(nlogn)
- 空間復雜度:O(n)
- 穩(wěn)定定：穩(wěn)定
- 優(yōu)劣
- 優(yōu)點：穩(wěn)定性舰蟆，性能不受輸入數(shù)據(jù)的影響
- 缺點：需要線性的額外空間
8. 基數(shù)排序
算法思想
先將所有關鍵字統(tǒng)一為相同位數(shù)，位數(shù)較少的數(shù)前邊補0.然后從最低位開始依次向高位進行排序狸棍，直到按最高位排序完成夭苗，關鍵字序列就成為有序序列「糇海基數(shù)排序基于分別排序题造，分別收集，所以是穩(wěn)定的猾瘸。適用于很長的數(shù)的排序界赔。
算法實現(xiàn)步驟
- 確定排序趟次，即確定最大的數(shù)的位數(shù)
- 從最低位按照分配和收集進行排序牵触，直至最高位淮悼。
- 在每一趟，分配按照相應關鍵字的曲子將記錄加入到r個不同的隊列揽思，收集是從小到大以此將r個隊列收尾相接成數(shù)組袜腥。
算法流程圖
基數(shù)排序
從圖片可以看出，最大的數(shù)只有3位钉汗，進行3趟排序羹令。先從個位進行排序，第二趟對十位數(shù)進行排序损痰，最后對百位數(shù)進行排序福侈。
Java代碼實現(xiàn)
/**
* 基數(shù)排序
*
* @param nums
*/
public static void radixSort(int []nums){
//確定排序趟次
int time = sortTime(nums);
//建立10個隊列
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> queue1 = new ArrayList<Integer>();
queue.add(queue1);
}
//進行time次分配和收集
for (int i = 0; i < time; i++) {
//分配數(shù)組元素;
for (int j = 0; j < nums.length; j++) {
//得到數(shù)字的第time+1位數(shù)
//先取余,再做除法
int x = nums[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> queue2 = queue.get(x);
queue2.add(nums[j]);
queue.set(x, queue2);
}
//元素計數(shù)器
int count = 0;
//收集隊列元素
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
//如果該隊列有分配到元素,對其進行收集
ArrayList<Integer> queue3 = queue.get(k);
nums[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
//查看第N趟排序后的結果
/*
System.out.print("\n"+"第"+i+"趟排序結果:");
for(int m=0;m<nums.length;m++){
System.out.print(nums[m]+" ");
}
*/
}
}
/**
* 計算基數(shù)排序的遍歷趟次
*
* @param nums 待排序序列
* @return 返回一個int類型,表示需要遍歷的趟次
*/
public static int sortTime(int []nums){
//首先確定排序的趟數(shù)
//通過待排序列的最大數(shù)來確定趟數(shù)time
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
int time = 0;
//判斷位數(shù);
while (max > 0) {
max /= 10;
time++;
}
return time;
}
算法分析
- 時間復雜度
- 最佳、最壞卢未、平均：O(mn)
- 空間復雜度:O(n)
- 穩(wěn)定性:穩(wěn)定
總結
| 算法 | 平均復雜度 | 最佳時間復雜度 | 最壞時間復雜度 | 空間復雜度 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(nlogn) | O(n) | O(n^2) | O(1) | 不穩(wěn)定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
| 冒泡排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
| 快速排序 | O(nlogn) | O(nlogn) | n(n^2) | O(nlogn) | 不穩(wěn)定 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩(wěn)定 |
| 基數(shù)排序 | O(nm) | O(nm) | O(nm) | O(n) | 穩(wěn)定 |
