排序
對(duì)一序列對(duì)象根據(jù)某個(gè)關(guān)鍵字進(jìn)行排序。
- 1、比較排序，時(shí)間復(fù)雜度O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序等。
- 2、非比較排序，時(shí)間復(fù)雜度可以達(dá)到O(n)，主要有：計(jì)數(shù)排序，基數(shù)排序，桶排序等。
一、Arrays類(lèi)的排序
通常情況下我們可以使用Array.sort()來(lái)對(duì)數(shù)組進(jìn)行排序
- Array.sort(int[] a) 直接對(duì)數(shù)組進(jìn)行升序排序
- Array.sort(int[] a , int fromIndex, int toIndex) 對(duì)數(shù)組的從fromIndex到toIndex進(jìn)行升序排序
二、排序算法
1、冒泡排序
- 算法思路：
1、比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
2、對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
3、針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
4、重復(fù)步驟1~3，直到排序完成。 - 動(dòng)圖展示：
- 代碼體現(xiàn)：
/*
*冒泡排序
*/
public static int[] bubbleSort(int[] array){
if(array.length()==0){
return array;
}else{
for(int i=0; i<array.length(); i++){
for(int j=0; j<array.length-1-i; j++){
if(array[j] > array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
return array;
}
}
最佳情況：T(n) = O(n) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(n2)
2、選擇排序
表現(xiàn)最穩(wěn)定的排序算法之一，因?yàn)?strong>無(wú)論什么數(shù)據(jù)進(jìn)去都是O(n2)的時(shí)間復(fù)雜度，所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。理論上講，選擇排序可能也是平時(shí)排序一般人想到的最多的排序方法了吧。
選擇排序(Selection-sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類(lèi)推，直到所有元素均排序完畢。
-
算法思路
n個(gè)記錄的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：
1、初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空；
2、第i趟排序(i=1,2,3…n-1)開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無(wú)序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)；
3、n-1趟結(jié)束，數(shù)組有序化了。
動(dòng)圖展示
- 代碼提現(xiàn)
/*
*選擇排序
*/
public static int[] selectionSort(int[] array){
if(array.length==0){
return array;
}else{
for(int i=0;i++;i<array.length()){
int minIndex=i;
for(int j=i;j++;j<array.length()){
if(array[j]<array[minIndex]){
minIndex=j;//將最小數(shù)的索引保存
}
}
int temp=array[minIndex];
array[minIndex]=array[i];
array[i]=temp;
}
return array;
}
}
最佳情況：T(n) = O(n2) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(n2)
3、快速排序
快速排序的基本思想：通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。
-
算法思路
快速排序使用分治法來(lái)把一個(gè)串（list）分為兩個(gè)子串（sub-lists）。具體算法描述如下：
1、從數(shù)列中挑出一個(gè)元素，稱(chēng)為 “基準(zhǔn)”（pivot）；
2、重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱(chēng)為分區(qū)（partition）操作；
3、遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
動(dòng)圖展示
- 代碼提現(xiàn)
/*
* 快速排序
*/
public static int QuickSort(int[] array,int start,int end){
if(array.length<1 || start<0 || end>array.length || start>end){
return null;
}else{
int smallIndex=partation(array,start,end);
if(smallIndex>start){
QuickSort(array, start, smallIndex - 1);
if (smallIndex < end)
QuickSort(array, smallIndex + 1, end);
return array;
}
}
}
//快速排序算法——partition
public static int partation(int[] array,int start,int end){
int povit=(int)(start+Math.random()*(end-start+1));
int smallIndex=start-1;
swap(array,pivot,end);
for(i=start;i<end;i++){
if(array[i]<array[end]){
smallIndex++;
if(i>smallIndex){
swap(array,i,smallIndex);
}
}
}
return smallIndex;
}
//交換數(shù)組內(nèi)兩個(gè)元素
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
