public static void insertionSort(int[] array){
int tmp;
for(int i=1;i<array.length;i ){
tmp = array[i]; //将當前位置的數給tmp
int j = i;
for(;j>0&&array[j-1]>tmp;j--){
/* * 往右移，騰出左邊的位置, * array[j-1]>tmp:大于号是升序排列，小于号是降序排列 */
array[j] = array[j-1];
}
//将當前位置的數插入到合适的位置
array[j] = tmp;
}
}
冒泡排序
- 基本思想：持續比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。直到沒有任何一對數字需要比較。
- 冒泡排序最好的時間複雜度為O(n)。冒泡排序的最壞時間複雜度為O(n2)。因此冒泡排序總的平均時間複雜度為O(n2)。
- 算法适用于少量數據的排序，是穩定的排序方法。
- 代碼：
public static void bubbleSort(int[] array){
int tmp;
boolean flag = false; //設置是否發生交換的标志
for(int i = array.length-1;i >= 0;i--){
for(int j=0;j<i;j ){ //每一輪都找到一個最大的數放在右邊
if(array[j]>array[j 1]){
tmp = array[j];
array[j] = array[j 1];
array[j 1] = tmp;
flag = true; //發生了交換
}
}
if(!flag) break; //這一輪循環沒有發生交換，說明排序已經完成，退出循環
}
}
選擇排序
- 基本思想：每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。
- 選擇排序是不穩定的排序方法。時間複雜度 O(n^2)。
- 代碼：
public static void selectSort(int[] array){
for(int i = 0;i<array.length-1;i ){
int min = array[i];
int minindex = i;
for(int j = i;j<array.length;j ){
if(array[j]<min){ //選擇當前最小的數
min = array[j];
minindex = j;
}
}
if(i != minindex){ //若i不是當前元素最小的，則和找到的那個元素交換
array[minindex] = array[i];
array[i] = min;
}
}
}
希爾排序
- 基本思想：先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組内進行直接插入排序；然後，取第二個增量d2<d1重複上述的分組和排序，直至所取的增量dt=1(dt<dt-1…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
- 在使用增量dk的一趟排序之後，對于每一個i，我們都有a[i]<=a[i dk],即所有相隔dk的元素都被排序。
- 希爾排序不穩定，時間複雜度 平均時間 O(nlogn) 最差時間O(n^2)
- 代碼：
public static void shellSort(int[] array){
int j;
for(int gap = array.length/2; gap>0; gap /= 2){
//定義一個增長序列，即分割數組的增量,d1=N/2 dk=(d(k-1))/2
for(int i = gap; i<array.length;i ){
int tmp = array[i];
for( j =i; j>=gap&&tmp<array[j-gap]; j -= gap){
//将相距為Dk的元素進行排序
array[j] = array[j-gap];
}
array[j] = tmp;
}
}
}
堆排序
- 預備知識：
- 二叉堆是完全二元樹（二叉樹）或者是近似完全二元樹（二叉樹）。 二叉堆有兩種：最大堆和最小堆。 大根堆：父結點的鍵值總是大于或等于任何一個子節點的鍵值； 小根堆：父結點的鍵值總是小于或等于任何一個子節點的鍵值。 二叉堆一般用數組來表示。例如，根節點在數組中的位置是0，第n個位置的子節點分别在2n 1和 2n 2。因此，第0個位置的子節點在1和2，1的子節點在3和4。以此類推。這種存儲方式便於尋找父節點和子節點。 例如初始要排序的數組為：49, 38, 65, 97, 76, 13, 27, 49 構造成大根堆之後的數組為：97 76 65 49 49 13 27 38 實際樹形結構如圖（最大堆）：
- 堆排序基本思想：在排序過程中，将R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的内在關系【參見二叉樹的順序存儲結構】，在當前無序區中選擇關鍵字最大(或最小)的記錄。堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特征，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
- 堆排序是一種選擇排序,其時間複雜度為O(nlogn)。堆排序是不穩定的
- 代碼：
/* * 堆排序 * 調整最大堆，交換根元素和最後一個元素。 * 參數說明： * a -- 待排序的數組 */
public static void heapSort(int[] a) {
int n = a.length;
int i,tmp;
// 從(n/2-1) --> 0逐次遍曆。遍曆之後，得到的數組實際上是一個(最大)二叉堆。
for (i = n / 2 - 1; i >= 0; i--)
maxHeapDown(a, i, n-1);
// 從最後一個元素開始對序列進行調整，不斷的縮小調整的範圍直到第一個元素
for (i = n - 1; i > 0; i--) {
// 交換a[0]和a[i]。交換後，a[i]是a[0...i]中最大的。
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
// 調整a[0...i-1]，使得a[0...i-1]仍然是一個最大堆。
// 即，保證a[i-1]是a[0...i-1]中的最大值。
maxHeapDown(a, 0, i-1);
}
}
/* * 注：數組實現的堆中，第N個節點的左孩子的索引值是(2N 1)，右孩子的索引是(2N 2)。 * 其中，N為數組下标索引值，如數組中第1個數對應的N為0。 * * 參數說明： * a -- 待排序的數組 * start -- 被下調節點的起始位置(一般為0，表示從第1個開始) * end -- 截至範圍(一般為數組中最後一個元素的索引) */
public static void maxHeapDown(int[] a, int start, int end) {
int c = start; // 當前(current)節點的位置
int l = 2*c 1; // 左(left)孩子的位置
int tmp = a[c]; // 當前(current)節點的大小
for (; l <= end; c=l,l=2*l 1) {
// "l"是左孩子，"l 1"是右孩子
if ( l < end && a[l] < a[l 1])
l ; // 左右兩孩子中選擇較大者，即m_heap[l 1]
if (tmp >= a[l])
break; // 調整結束
else { // 交換值
a[c] = a[l];
a[l]= tmp;
}
}
}
歸并排序
- 歸并排序的原理：
- 将待排序的數組分成前後兩個部分，再遞歸的将前半部分數據和後半部分的數據各自歸并排序，得到的兩部分數據，然後使用merge合并算法（算法見代碼）将兩部分算法合并到一起。 例如：如果N=1；那麼隻有一個數據要排序，N=2，隻需要調用merge函數将前後合并，N=4，........... 也就是将一個很多數據的數組分成前後兩部分，然後不斷遞歸歸并排序，再合并，最後返回有序的數組。
- 歸并排序的時間複雜度：
- 歸并排序的最好、最壞和平均時間複雜度都是O(nlogn)，而空間複雜度是O(n)，比較次數介于(nlogn)/2和(nlogn)-n 1，賦值操作的次數是(2nlogn)。因此可以看出，歸并排序算法比較占用内存，但卻是效率高且穩定的排序算法。
- 代碼：
public class MergeSort {
private static void mergeSort(int[] array,int[] tmp,int left,int right){
if(left<right){
int center = ( left right ) / 2;//取數組的中點
mergeSort(array,tmp,left,center);//歸并排序數組的前半部分
mergeSort(array,tmp,center 1,right);//歸并排序數組的後半部分
merge(array,tmp,left,center 1,right);//将數組的前後半部分合并
}
}
/* * 超簡單的合并函數 */
private static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) {
// TODO Auto-generated method stub
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos 1;
while(leftPos <= leftEnd && rightPos <= rightEnd){
if(array[leftPos]<=array[rightPos]){
tmp[tmpPos ] = array[leftPos ];
}else{
tmp[tmpPos ] = array[rightPos ];
}
}
while(leftPos <= leftEnd){
tmp[tmpPos ] = array[leftPos ];
}
while(rightPos <= rightEnd){
tmp[tmpPos ] = array[rightPos ];
}
for(int i=0;i<numElements;i ,rightEnd--){
array[rightEnd] = tmp[rightEnd];
}
}
public static void mergeSort(int[] array){
int[] tmp = new int[array.length];//聲明一個用來合并的數組
mergeSort(array,tmp,0,array.length-1);//調用排序函數，傳入數字的起點和終點
}
}
快速排序
- 快速排序原理：
- 如果數組S中元素是0或者1，則返回；
- 區數組S中任一元素v，稱之為樞紐元；
- 将S-{v}（S中剩餘的元素）劃分成連個不相交的集合：S1={S-{v}|x<=v}和S2={S-{v}|x>=v};
- 返回{quicksort(s1)}後跟v，繼而返回{quicksort(S2)}。
- 選取樞紐元（三數中值分割法）
- 一般的做法是使用左端、右端和中心位置上的三個元素的中值作為基元。 分割策略： 在分割階段吧所有小元素移到數組的左邊，大元素移到數組右邊。，大小是相對于樞紐元素而言的。 當i在j的左邊時，将i右移，移過哪些小于樞紐元的元素，并将j左移，已過那些大于樞紐元的元素，當i和j停止時，i指向一個大元素，而j指向一個小元素，如果i在j的左邊，那麼将這兩個元素交換，其效果是把一個大元素推向右邊，而把小元素推向左邊。
- 速排序平均時間複雜度為O(nlogn)，最壞情況為O(n^2)，n越大，速度越快。不是穩定的排序算法。
- 代碼：
/* * 快速排序 * 兩個方向，左邊的i下标一直往右走，當a[i] <= a[center_index]， * 其中center_index是中樞元素的數組下标，而右邊的j下标一直往左走，當a[j] > a[center_index] * 如果i和j都走不動了，i <= j, 交換a[i]和a[j],重複上面的過程，直到i>j * 交換a[j]和a[center_index]，完成一趟快速排序 * 樞軸采用三數中值分割法可以優化 */
//遞歸快速排序
public static void quickSort(int a[]){
qSort(a, 0, a.length - 1);
}
//遞歸排序，利用兩路劃分
public static void qSort(int a[],int low,int high){
int pivot = 0;
if(low < high){
//将數組一分為二
pivot = partition(a,low,high);
//對第一部分進行遞歸排序
qSort(a,low,pivot);
//對第二部分進行遞歸排序
qSort(a,pivot 1,high);
}
}
//partition函數，實現三數中值分割法
public static int partition(int a[],int low,int high){
int pivotkey = a[low]; //選取第一個元素為樞軸記錄
while(low < high){
//将比樞軸記錄小的交換到低端
while(low < high && a[high] >= pivotkey){
high--;
}
//采用替換而不是交換的方式操作
a[low] = a[high];
//将比樞軸記錄大的交換到高端
while(low < high && a[low] <= pivotkey){
low ;
}
a[high] = a[low];
}
//樞紐所在位置賦值
a[low] = pivotkey;
//返回樞紐所在的位置
return low;
}
桶式排序
- 桶式排序不再是一種基于比較的排序方法，它是一種比較巧妙的排序方式，但這種排序方式需要待排序的序列滿足以下兩個特征： 待排序列所有的值處于一個可枚舉的範圍之類； 待排序列所在的這個可枚舉的範圍不應該太大，否則排序開銷太大。
- 排序的具體步驟如下：
- (1)對于這個可枚舉範圍構建一個buckets數組，用于記錄“落入”每個桶中元素的個數；
- (2)将（1）中得到的buckets數組重新進行計算，按如下公式重新計算：
- buckets[i] = buckets[i] buckets[i-1] (其中1<=i<buckets.length);
- 桶式排序是一種非常優秀的排序算法，時間效率極高，它隻要通過2輪遍曆：第1輪遍曆待排數據，統計每個待排數據“落入”各桶中的個數，第2輪遍曆buckets用于重新計算buckets中元素的值，2輪遍曆後就可以得到每個待排數據在有序序列中的位置，然後将各個數據項依次放入指定位置即可。
- 桶式排序的空間開銷較大，它需要兩個數組，第1個buckets數組用于記錄“落入”各桶中元素的個數，進而保存各元素在有序序列中的位置，第2個數組用于緩存待排數據.
- 桶式排序是穩定的。如果待排序數據的範圍在0~k之間，那麼它的時間複雜度是O(k n)的.
- 但是它的限制多，比如它隻能排整形數組。而且當k較大，而數組長度n較小，即k>>n時，輔助數組C[k 1]的空間消耗較大。當數組為整形，且k和n接近時, 可以用此方法排序。
- 代碼實現：
//min的值為0，max的值為待排序數組中最大值 1
public static void bucketSort(int[] data, int min, int max) {
// 緩存數組
int[] tmp = new int[data.length];
// buckets用于記錄待排序元素的信息
// buckets數組定義了max-min個桶
int[] buckets = new int[max - min];
// 計算每個元素在序列出現的次數
for (int i = 0; i < data.length; i ) {
buckets[data[i] - min] ;
}
// 計算“落入”各桶内的元素在有序序列中的位置
for (int i = 1; i < max - min; i ) {
buckets[i] = buckets[i] buckets[i - 1];
}
// 将data中的元素完全複制到tmp數組中
System.arraycopy(data, 0, tmp, 0, data.length);
// 根據buckets數組中的信息将待排序列的各元素放入相應位置
for (int k = data.length - 1; k >= 0; k--) {
data[--buckets[tmp[k] - min]] = tmp[k];
}
}
總結
- 下面是一個總的表格，大緻總結了我們常見的所有的排序算法的特點。
- 性能測試
,
更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
