今天,準(zhǔn)備填完昨天沒填的坑,將排序算法方面的知識系統(tǒng)的學(xué)習(xí)一下,但是在簡單的了解了一下后,有些不知如何組織學(xué)習(xí)了,因?yàn)榕判蛩惴ǖ姆N類,實(shí)在是太多了,各有優(yōu)略,各有適用的場景.有些不知所措,從何開始.
最后按照常規(guī)思路,我將逐次從排序算法的了解,常用的幾種排序算法的原理及實(shí)現(xiàn),幾種算法的對比以及適用場景.三個方面展開對排序算法的學(xué)習(xí).
-
排序算法的基本了解
在我們學(xué)習(xí)一樣知識,技術(shù)之前,首先我們應(yīng)當(dāng)對它有一個基本的了解,然后在了解的基礎(chǔ)上逐漸深入學(xué)習(xí).
在計算機(jī)科學(xué)與數(shù)學(xué)中矛绘，排序算法（Sorting algorithm）是一種能將一串?dāng)?shù)據(jù)依照特定排序方式進(jìn)行排列的一種算法。最常用到的排序方式是數(shù)值順序以及字典順序刃永。有效的排序算法在一些算法例如搜索算法與合并算法中是重要的.基本上货矮，排序算法的輸出必須遵守下列兩個原則：
- 輸出結(jié)果為遞增序列（遞增是針對所需的排序順序而言）
- 輸出結(jié)果是原輸入的一種排列、或是重組
而在計算機(jī)科學(xué)種關(guān)于排序算法的分類,也十分有趣,是直接按照排序算法的性能分類的,而排序算法的性能又是以時間復(fù)雜度,空間復(fù)雜度來判斷的,而在排序算法中,主要被考慮到的當(dāng)然就是時間復(fù)雜度了,畢竟一組數(shù)據(jù)的排序快慢是可以很直觀的影響到其性能的.
- 時間復(fù)雜度與空間復(fù)雜度
時間復(fù)雜度,就是一個定性描述算法執(zhí)行時間的函數(shù).空間復(fù)雜度是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量度.
由于時間復(fù)雜度的定義比較難以使人理解,我將另寫一篇文章,全面總結(jié)和學(xué)習(xí)一下時間復(fù)雜度和空間復(fù)雜度的相關(guān)知識,這里就不大篇幅的來進(jìn)行說明了.
幾種常用的排序算法的探討
排序算法是真的有很多,
2019-4-6-01.png
經(jīng)過選擇,在這里選取其中最常使用到的6種排序算法進(jìn)行探討,關(guān)于一些較特殊的,高級的算法在之后需要使用到的時候再去學(xué)習(xí).
- 最基本的冒泡,選擇,插入排序
- 進(jìn)階級別的希爾,歸并,快速排序
-
算法的實(shí)現(xiàn)原理
-
冒泡排序
冒泡排序,作為最簡單的最基礎(chǔ)的排序方法,被廣為人知,其是在排序算法問題之初就自然而然使人想到并運(yùn)用到的排序算法,可以稱之為排序算法的基礎(chǔ).
其算法思路是通過循環(huán)不斷對比相鄰的兩個數(shù)據(jù),使小的向前,大的向后,兩者交換,較小的數(shù)像氣泡一樣不斷上浮,最終完成排序,因此形象的稱之為冒泡排序.
冒泡排序
/**
* 冒泡排序
* 通過兩個for循環(huán)來排序數(shù)組
* 外層循環(huán)控制需要循環(huán)的輪次
* 內(nèi)層循環(huán)控制相鄰元素的對比及交換.
*/
public void BubbleSort(int[] arr){
long startime = System.nanoTime(); // 記錄程序開始運(yùn)行的時間點(diǎn)
for (int i=1;i<arr.length;i++){ // 外層for循環(huán)
for (int j=0;j<arr.length-i;j++){ //內(nèi)層for循環(huán),arr.length-i表示每進(jìn)行完一輪就將循環(huán)對比的的次數(shù)減小一次,因?yàn)樽詈竺娴捻樞蚨际敲看窝h(huán)中最大的,順序已經(jīng)排好,不需要再進(jìn)行對比了.
if (arr[j]>arr[j+1]){ //判斷交換的條件,如果當(dāng)前元素比后一個元素大就交換兩者位置
int a=arr[j+1]; // 兩個數(shù)的交換代碼
arr[j+1]=arr[j];
arr[j]=a;
}
}
}
System.out.println(Arrays.toString(arr));
long endtime = System.nanoTime(); // 記錄程序結(jié)束的時間點(diǎn)
System.out.println("運(yùn)行時間:"+(endtime-startime)+"ns"); // 輸出程序運(yùn)行的時間(開始結(jié)束的時間差)
}
-
選擇排序
選擇排序算法思想是在末未排序的序列中找到最小的一個元素,然后和當(dāng)前的首位元素交換位置,之后在循環(huán)在未排序的序列中找到最小的元素,將其插入到已排序的末尾位置.
選擇排序
/**
* 選擇排序
* 選擇排序也是通過兩個for循環(huán)來實(shí)現(xiàn)的
* 外層for循環(huán)控制循環(huán)輪次,總共n-1輪
* 此外我們還需要聲明一個局部變量記錄每次循環(huán)對比的最小元素的下標(biāo).
* 內(nèi)存for循環(huán),通過依次對比比較,將當(dāng)前未排序的序列中最小元素的下標(biāo)記錄下來.
*最后通過if判斷找到的下標(biāo)與最開始的下標(biāo)i是否相同,不相同就交換兩者對應(yīng)的元素
*/
public void Selectsort(int[] arr){
System.out.println("選擇排序:");
long startime = System.nanoTime();
for(int i=0;i<arr.length-1;i++){ // 控制循環(huán)的輪次,總共需要n-1次.
int min =i; // 聲明成員變量,用來儲存最小元素的下標(biāo).
for(int j=i+1;j<arr.length;j++){ // 內(nèi)層for循環(huán),j=i+1是為了將序列分開為i表示的已排列,和i+1及之后的未排列兩部分,
if(arr[j]<arr[min]){ // 判斷條件,在未排列(即i+1之后的序列.)序列里找到最小元素
min =j; // 將最小元素的下標(biāo)保存到成員變量min中
}
}
if(min !=i){ // 判斷條件,判斷最小元素是否和當(dāng)前首位元素相同,
// 交換位置.
int a=arr[i];
arr[i]=arr[min];
arr[min]=a;
}
}
System.out.println(Arrays.toString(arr)); // Arrays類的toAString方法,遍歷輸出數(shù)組
long endtime=System.nanoTime();
System.out.println("運(yùn)行時間:"+(endtime-startime)+"ns");
}
-
插入排序
插入排序的算法思路也是將序列分為已排序和未排序兩部分,然后從未排序的首位開始,依次和已排序的每個元素對比,大于或等于就插在該元素后一位,小于就插入到該元素前一位.插入排序是最容易理解的排序方法,其就像我們打撲克是的插牌一樣.
插入排序
/**
* 插入排序
*插入排序也是通過嵌套循環(huán)實(shí)現(xiàn)排序的.
* y原始案例通過for,while循環(huán)嵌套實(shí)現(xiàn),
*/
public void Insertsort(int[] arr){
long startime=System.nanoTime();
System.out.println("插入排序:");
int[] copyarr=Arrays.copyOf(arr,23); // 復(fù)制數(shù)組,以防改變了數(shù)組arr.
for (int i=1;i<copyarr.length;i++){ //外層循環(huán)控制輪次.
int tmp=copyarr[i]; //將當(dāng)前未排序的序列首位元素抽出.
int j=i-1; // 定義局部變量 j代表i前面的已排序序列的末位
while(j>=0 && copyarr[j]>tmp){ // while循環(huán)控制,從已排序末位逐漸往前對比,如果比tmp大.
copyarr[j+1]=copyarr[j]; //就交換兩者值,
j--; // j自減一,實(shí)現(xiàn)循環(huán)比較交換,排序
}
copyarr[j+1]=tmp; // 其他條件下,說明tmp就是當(dāng)前的最小值,直接將tmp賦值給copyarr[j+1].
}
System.out.println(Arrays.toString(copyarr));
long endtime=System.nanoTime();
System.out.println("運(yùn)行時間:"+(endtime-startime)+"ns");
}
冒泡排序,選擇排序,插入排序,都是最早,最簡單演變下的排序算法,其時間復(fù)雜度相同,是最慢的排序算法,其在循環(huán)上進(jìn)行了太多的重復(fù)性,無意義的循環(huán)操作.
- 希爾排序
希爾排序也是一種遞增減量算法,是插入排序的更高效的版本.希爾排序主要根據(jù)插入排序的兩點(diǎn)改進(jìn)的:- 當(dāng)插入排序在處理趨近于正序的的序列時,效率最高,可以趨近于線性排序的效率.
- 插入排序每次只對一個數(shù)據(jù)進(jìn)行操作移動,無疑使其效率低化.
希爾排序的基本思路:先將待排序列分為若干個子序列,再分別使用插入排列.在基本有序之后,再全部序列進(jìn)行插入排列.也就是分組插入排列加插入排列.
希爾排列
/**
* 希爾排列
* 希爾排列是插入排列的進(jìn)階版
* 相當(dāng)于將無序序列分成為多個子級無序序列,再分別進(jìn)行插入排列.
*/
public void Shellsort(int[] arr) {
long startime = System.nanoTime();
System.out.println("希爾排序:");
int[] copyarr = Arrays.copyOf(arr, 23);
for (int gap = copyarr.length / 2; gap > 0; gap /= 2) { // for循環(huán)控制分組情況,每次循環(huán)將序列拆分為兩組直到不能拆分為止.
for (int j = gap; j < copyarr.length; j++) { //然后通過for循環(huán)控制每組無序序列直接進(jìn)行插入排序
int temp = copyarr[j];
int k;
for (k = j - gap; k >= 0 && copyarr[k] > temp; k -= gap) {
copyarr[k + gap] = copyarr[k];
}
copyarr[k + gap] = temp;
}
}
System.out.println(Arrays.toString(copyarr));
long endtime = System.nanoTime();
System.out.println("運(yùn)行時間:" + (endtime - startime) + "ns");
}
-
歸并排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法斯够。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用囚玫。歸并排序是一個十分高效的排序方法,并且其在任何情況下,時間復(fù)雜度都是相同的,但高效的同時,必然會犧牲一定的內(nèi)存空間,由于歸并排序需要一塊額外的內(nèi)存儲存數(shù)組,所以可以說占用額外的內(nèi)存空間是它唯一的缺點(diǎn),這一點(diǎn)也注定了,它將不適合大型,大規(guī)模數(shù)據(jù)的排序.
其實(shí)現(xiàn)思路是,通過遞歸,或迭代的方式,將序列分成兩個有序的序列,然后比較合并兩個有序序列.合并兩個有序序列是十分高效的.可以取景于O(n).
歸并排序
歸并排序的原理圖解:
2019-4-7-01.png
分,即通過遞歸不斷分組,治,將排序好的分組合并.
/**
* 歸并排序
* 這里通過兩個方法的調(diào)用實(shí)現(xiàn).
* mergesort方法,主要將數(shù)組copy并分為左右兩個序列.
* 通過調(diào)用本身實(shí)現(xiàn)不斷的分化.
*/
public int[] Mergesort(int[] arr){
int[] copyarr = Arrays.copyOf(arr, arr.length);
if (copyarr.length<2){
return copyarr;
}
int middle =(int)Math.floor(copyarr.length / 2); // 將序列的長度一分為二.
int[] left = Arrays.copyOfRange(copyarr, 0, middle);
int[] right = Arrays.copyOfRange(copyarr, middle, copyarr.length);
// 返回值調(diào)用合并方法,將排序后的分組不斷合并.最后返回一個完整的排序后的序列.
return merge(Mergesort(left),Mergesort(right));
}
protected int[] merge(int[] left, int[] right) { //傳參,將左右兩個無序序列傳進(jìn)來.
int[] result = new int[left.length + right.length]; //定義一個新的空數(shù)組,長度為左右序列的長度之和,
int i = 0; // 聲明一個成員變量i.
while (left.length > 0 && right.length > 0) { // while 循環(huán)控制條件
if (left[0] <= right[0]) { // if判斷語句,判斷左右序列對應(yīng)位置元素的大小.
result[i++] = left[0]; // 然后將小的元素存放在合并數(shù)組的對應(yīng)位置中.
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while(left.length>0){ // 不滿足以上while條件跳出循環(huán)時,執(zhí)行,
result[i++] = left[0];
left = Arrays.copyOfRange(left,1,left.length);
}
while(right.length>0){
result[i++] = right[0];
right = Arrays.copyOfRange(right,1,right.length);
}
return result; // 返回排序合并后的序列.
}
- 快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下读规，排序 n 個項(xiàng)目要 Ο(nlogn) 次比較抓督。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見掖桦。事實(shí)上本昏，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來枪汪。
快速排序也是在分治思想上的又一經(jīng)典的應(yīng)用,在大部分情況下,快速排序總是最高效的,比歸并排序還要高效的多,且其適用于大多所情況下,在無序的隨機(jī)數(shù)排序上表現(xiàn)也要好的多,但同時它的缺點(diǎn)也很明顯,它的時間按復(fù)雜并不固定,存在最壞情況,時間復(fù)雜度波動非常大,且其實(shí)現(xiàn)思路也是基于遞歸思想的,其空間復(fù)雜度會很高,占用額外的內(nèi)存.
本質(zhì)上,快速排序是在冒泡排序的基礎(chǔ)上演變而來的分而治之的思想,其思路是:從序列中挑選一個基準(zhǔn)值,將大于該數(shù)的數(shù)放在該基準(zhǔn)的右邊,小的放在左邊,然后使用遞歸,依次將兩邊的序列排序.
快速排序
/**
* 快速排序
*快速排序是分而治之的經(jīng)典應(yīng)用之一
* 通過遞歸調(diào)用的方式實(shí)現(xiàn)排序,
* 在大多情況下,其效率是最高的.
*/
public int[] sort(int[] arr){ // sort 方法 用來出copy數(shù)組,并調(diào)用排序方法.
int[] copyarr=Arrays.copyOf(arr,arr.length);
return quicksort(copyarr,0,copyarr.length-1);
}
// 快速排序方法.
private int[] quicksort(int[] arr,int left,int right){ //傳入?yún)?shù),待排序的數(shù)組,左下標(biāo),及數(shù)組長度減1.
if(left<right){ // if判斷條件,這里沒有else是因?yàn)閘eft必然是小于right的.如果等于的話,直接返回數(shù)組就可以了.
int partitionindex = partition(arr,left,right); // 聲明局部變量,調(diào)用分區(qū)方法,遞歸調(diào)用.
quicksort(arr,left,partitionindex-1); //
quicksort(arr,partitionindex+1,right); // 遞歸調(diào)用本身,
}
return arr;
}
/**
* 分區(qū)方法,將無序序列以基準(zhǔn)為界分別放在左右兩邊,
* 真正的比較交換操作,是在這個分區(qū)方法里實(shí)現(xiàn)的.
* 然后在通過前面的遞歸調(diào)用,來循環(huán)使用分區(qū)方法,實(shí)現(xiàn)排序.
*/
private int partition(int[] arr,int left,int right){
int pivot =left;
int index = pivot+1;
for (int i=index;i<=right;i++){
if (arr[i]<arr[pivot]){
swap(arr,i,index);
index++;
}
}
swap(arr,pivot,index-1);
return index-1;
}
// 封裝通用方法,將數(shù)組arr中的arr[i]與arr[j]的值交換
private void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
- 源代碼
package day_4_6;
import java.util.Arrays;
/**
* @outhor xiaoshe
* @date 2019/4/6 - @time 11:20
* 排序算法
*/
public class Sty_Sortalgrithm {
public static void main(String[] args) {
int[] arr = {5, 2, 4, 1, 3, 7, 9, 5, 6, 8, 0, 9, 10, 13, 11, 15, 12, 17, 14, 13, 18, 19, 20};
Sty_Sortalgrithm sortalgrithm = new Sty_Sortalgrithm();
sortalgrithm.BubbleSort(arr);
sortalgrithm.Selectsort(arr);
sortalgrithm.Insertsort(arr);
sortalgrithm.Shellsort(arr);
System.out.println("歸并排序:");
System.out.println(Arrays.toString(sortalgrithm.Mergesort(arr)));
System.out.println("快速排序:");
System.out.println(Arrays.toString(sortalgrithm.sort(arr)));
}
/**
* 冒泡排序
* 通過兩個for循環(huán)來排序數(shù)組
* 外層循環(huán)控制需要循環(huán)的輪次
* 內(nèi)層循環(huán)控制相鄰元素的對比及交換.
*/
public void BubbleSort(int[] arr) {
long startime = System.nanoTime(); // 記錄程序開始運(yùn)行的時間點(diǎn)
int[] copyarr = Arrays.copyOf(arr, 23);
System.out.println("冒泡排序:");
for (int i = 1; i < copyarr.length; i++) { // 外層for循環(huán)
for (int j = 0; j < copyarr.length - i; j++) { //內(nèi)層for循環(huán),arr.length-i表示每進(jìn)行完一輪就將循環(huán)對比的的次數(shù)減小一次,因?yàn)樽詈竺娴捻樞蚨际敲看窝h(huán)中最大的,順序已經(jīng)排好,不需要再進(jìn)行對比了.
if (copyarr[j] > copyarr[j + 1]) { //判斷交換的條件,如果當(dāng)前元素比后一個元素大就交換兩者位置
int a = copyarr[j + 1]; // 兩個數(shù)的交換代碼
copyarr[j + 1] = copyarr[j];
copyarr[j] = a;
}
}
}
System.out.println(Arrays.toString(copyarr)); // Arrays類中的toString方法遍歷輸出數(shù)組.
long endtime = System.nanoTime(); // 記錄程序結(jié)束的時間點(diǎn)
System.out.println("運(yùn)行時間:" + (endtime - startime) + "ns"); // 輸出程序運(yùn)行的時間(開始結(jié)束的時間差)
}
/**
* 選擇排序
* 選擇排序也是通過兩個for循環(huán)來實(shí)現(xiàn)的
* 外層for循環(huán)控制循環(huán)輪次,總共n-1輪
* 此外我們還需要聲明一個局部變量記錄每次循環(huán)對比的最小元素的下標(biāo).
* 內(nèi)存for循環(huán),通過依次對比比較,將當(dāng)前未排序的序列中最小元素的下標(biāo)記錄下來.
* 最后通過if判斷找到的下標(biāo)與最開始的下標(biāo)i是否相同,不相同就交換兩者對應(yīng)的元素
*/
public void Selectsort(int[] arr) {
long startime = System.nanoTime();
int[] copyarr = Arrays.copyOf(arr, 23);
System.out.println("選擇排序:");
for (int i = 0; i < copyarr.length - 1; i++) { // 控制循環(huán)的輪次,總共需要n-1次.
int min = i; // 聲明成員變量,用來儲存最小元素的下標(biāo).
for (int j = i + 1; j < copyarr.length; j++) { // 內(nèi)層for循環(huán),j=i+1是為了將序列分開為i表示的已排列,和i+1及之后的未排列兩部分,
if (copyarr[j] < copyarr[min]) { // 判斷條件,在未排列(即i+1之后的序列.)序列里找到最小元素
min = j; // 將最小元素的下標(biāo)保存到成員變量min中
}
}
if (min != i) { // 判斷條件,判斷最小元素是否和當(dāng)前首位元素相同,
// 交換位置.
int a = copyarr[i];
copyarr[i] = copyarr[min];
copyarr[min] = a;
}
}
System.out.println(Arrays.toString(copyarr)); // Arrays類的toAString方法,遍歷輸出數(shù)組
long endtime = System.nanoTime();
System.out.println("運(yùn)行時間:" + (endtime - startime) + "ns");
}
/**
* 插入排序
* 插入排序也是通過嵌套循環(huán)實(shí)現(xiàn)排序的.
* y原始案例通過for,while循環(huán)嵌套實(shí)現(xiàn),
*/
public void Insertsort(int[] arr) {
long startime = System.nanoTime();
System.out.println("插入排序:");
int[] copyarr = Arrays.copyOf(arr, 23); // 復(fù)制數(shù)組,以防改變了數(shù)組arr.
for (int i = 1; i < copyarr.length; i++) { //外層循環(huán)控制輪次.
int temp = arr[i]; // 聲明temp,將此時未排序的首位元素抽出.
int j;
for (j = i - 1; j >= 0 && copyarr[j] > temp; j--) { // 內(nèi)存for循環(huán)和判斷條件合并.
//當(dāng)無序序列首位元素(temp)小于有序序列末尾元素(copyarr[j])時
//就將j的值賦給j+1,這里的j+1=i;之所以使用j+1是為了能夠在條件不滿足時在內(nèi)層for循環(huán)中循環(huán)進(jìn)行判斷.
copyarr[j + 1] = copyarr[j];
}
copyarr[j + 1] = temp; //在外層循環(huán)其他條件下,直接將temp賦值給j+1
}
System.out.println(Arrays.toString(copyarr));
long endtime = System.nanoTime();
System.out.println("運(yùn)行時間:" + (endtime - startime) + "ns");
}
/**
* 希爾排序
* 希爾排列是插入排列的進(jìn)階版
* 相當(dāng)于將無序序列分成為多個子級無序序列,再分別進(jìn)行插入排列.
*/
public void Shellsort(int[] arr) {
long startime = System.nanoTime();
System.out.println("希爾排序:");
int[] copyarr = Arrays.copyOf(arr, 23);
for (int gap = copyarr.length / 2; gap > 0; gap /= 2) { // for循環(huán)控制分組情況,每次循環(huán)將序列拆分為兩組直到不能拆分為止.
for (int j = gap; j < copyarr.length; j++) { //然后通過for循環(huán)控制每組無序序列直接進(jìn)行插入排序
int temp = copyarr[j];
int k;
for (k = j - gap; k >= 0 && copyarr[k] > temp; k -= gap) {
copyarr[k + gap] = copyarr[k];
}
copyarr[k + gap] = temp;
}
}
System.out.println(Arrays.toString(copyarr));
long endtime = System.nanoTime();
System.out.println("運(yùn)行時間:" + (endtime - startime) + "ns");
}
/**
* 歸并排序
* 這里通過兩個方法的調(diào)用實(shí)現(xiàn).
* mergesort方法,主要將數(shù)組copy并分為左右兩個序列.
* 通過調(diào)用本身實(shí)現(xiàn)不斷的分化.
*/
public int[] Mergesort(int[] arr){
int[] copyarr = Arrays.copyOf(arr, arr.length);
if (copyarr.length<2){
return copyarr;
}
int middle =(int)Math.floor(copyarr.length / 2); // 將序列的長度一分為二.
int[] left = Arrays.copyOfRange(copyarr, 0, middle);
int[] right = Arrays.copyOfRange(copyarr, middle, copyarr.length);
// 返回值調(diào)用合并方法,將排序后的分組不斷合并.最后返回一個完整的排序后的序列.
return merge(Mergesort(left),Mergesort(right));
}
protected int[] merge(int[] left, int[] right) { //傳參,將左右兩個無序序列傳進(jìn)來.
int[] result = new int[left.length + right.length]; //定義一個新的空數(shù)組,長度為左右序列的長度之和,
int i = 0; // 聲明一個成員變量i.
while (left.length > 0 && right.length > 0) { // while 循環(huán)控制條件
if (left[0] <= right[0]) { // if判斷語句,判斷左右序列對應(yīng)位置元素的大小.
result[i++] = left[0]; // 然后將小的元素存放在合并數(shù)組的對應(yīng)位置中.
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while(left.length>0){ // 不滿足以上while條件跳出循環(huán)時,執(zhí)行,
result[i++] = left[0];
left = Arrays.copyOfRange(left,1,left.length);
}
while(right.length>0){
result[i++] = right[0];
right = Arrays.copyOfRange(right,1,right.length);
}
return result; // 返回排序合并后的序列.
}
/**
* 快速排序
*快速排序是分而治之的經(jīng)典應(yīng)用之一
* 通過遞歸調(diào)用的方式實(shí)現(xiàn)排序,
* 在大多情況下,其效率是最高的.
*/
public int[] sort(int[] arr){ // sort 方法 用來出copy數(shù)組,并調(diào)用排序方法.
int[] copyarr=Arrays.copyOf(arr,arr.length);
return quicksort(copyarr,0,copyarr.length-1);
}
// 快速排序方法.
private int[] quicksort(int[] arr,int left,int right){ //傳入?yún)?shù),待排序的數(shù)組,左下標(biāo),及數(shù)組長度減1.
if(left<right){ // if判斷條件,這里沒有else是因?yàn)閘eft必然是小于right的.如果等于的話,直接返回數(shù)組就可以了.
int partitionindex = partition(arr,left,right); // 聲明局部變量,調(diào)用分區(qū)方法,遞歸調(diào)用.
quicksort(arr,left,partitionindex-1); //
quicksort(arr,partitionindex+1,right); // 遞歸調(diào)用本身,
}
return arr;
}
/**
* 分區(qū)方法,將無序序列以基準(zhǔn)為界分別放在左右兩邊,
* 真正的比較交換操作,是在這個分區(qū)方法里實(shí)現(xiàn)的.
* 然后在通過前面的遞歸調(diào)用,來循環(huán)使用分區(qū)方法,實(shí)現(xiàn)排序.
*/
private int partition(int[] arr,int left,int right){
int pivot =left;
int index = pivot+1;
for (int i=index;i<=right;i++){
if (arr[i]<arr[pivot]){
swap(arr,i,index);
index++;
}
}
swap(arr,pivot,index-1);
return index-1;
}
// 封裝通用方法,將數(shù)組arr中的arr[i]與arr[j]的值交換
private void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
-
算法的比較與使用
關(guān)于個排序算法的復(fù)雜度,穩(wěn)定性,等信息的對比,可以參照下面這張圖:
2019-4-7-02.png
根據(jù)前面的學(xué)些了解的特性,最基本的三種排序,冒泡,選擇,插入排序,在小規(guī)模數(shù)據(jù)的排序上,表現(xiàn)會好些,在序列趨近于正序時,冒泡和插入更高效,.
歸并排序是最穩(wěn)定的排序算法,其在不同情況下的時間復(fù)雜度不會有多大變化,而在對大量無序隨機(jī)數(shù)排序時,快排的效率時最高的,但,歸并排序和快速排序?qū)?nèi)存有一定要求,不適合需要控制內(nèi)存使用的情況.
更新時間:
2019-4-7
3:14
