1难礼、冒泡排序
最簡單的一種排序算法娃圆。假設(shè)長度為n的數(shù)組arr，要按照從小到大排序蛾茉。則冒泡排序的具體過程可以描述為：首先從數(shù)組的第一個(gè)元素開始到數(shù)組最后一個(gè)元素為止讼呢，對數(shù)組中相鄰的兩個(gè)元素進(jìn)行比較，如果位于數(shù)組左端的元素大于數(shù)組右端的元素谦炬，則交換這兩個(gè)元素在數(shù)組中的位置悦屏，此時(shí)數(shù)組最右端的元素即為該數(shù)組中所有元素的最大值。接著對該數(shù)組剩下的n-1個(gè)元素進(jìn)行冒泡排序键思，直到整個(gè)數(shù)組有序排列础爬。算法的時(shí)間復(fù)雜度為O(n^2)。
// 冒泡排序
void BubbleSort(int arr[], int length)
{
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp;
temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
2吼鳞、選擇排序
嚴(yán)蔚敏版《數(shù)據(jù)結(jié)構(gòu)》中對選擇排序的基本思想描述為：每一趟在n-i+1(i=1,2,...,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄看蚜。具體來說，假設(shè)長度為n的數(shù)組arr赔桌，要按照從小到大排序供炎，那么先從n個(gè)數(shù)字中找到最小值min1，如果最小值min1的位置不在數(shù)組的最左端(也就是min1不等于arr[0])疾党，則將最小值min1和arr[0]交換音诫，接著在剩下的n-1個(gè)數(shù)字中找到最小值min2，如果最小值min2不等于arr[1]雪位，則交換這兩個(gè)數(shù)字竭钝，依次類推，直到數(shù)組arr有序排列茧泪。算法的時(shí)間復(fù)雜度為O(n^2)蜓氨。
// 選擇排序
void SelectionSort(int arr[], int length)
{
for (int i = 0; i < length; i++)
{
int index = i;
for (int j = i+1; j < length; j++)
{
if (arr[j] < arr[index])
{
index = j;
}
}
if (index == i)
continue;
else
{
int temp;
temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}
}
3、插入排序
插入排序的基本思想就是將無序序列插入到有序序列中队伟。例如要將數(shù)組arr=[4,2,8,0,5,1]排序穴吹，可以將4看做是一個(gè)有序序列(圖中用藍(lán)色標(biāo)出)，將[2,8,0,5,1]看做一個(gè)無序序列嗜侮。無序序列中2比4小港令，于是將2插入到4的左邊啥容，此時(shí)有序序列變成了[2,4]，無序序列變成了[8,0,5,1]顷霹。無序序列中8比4大咪惠，于是將8插入到4的右邊，有序序列變成了[2,4,8],無序序列變成了[0,5,1]淋淀。以此類推遥昧，最終數(shù)組按照從小到大排序。該算法的時(shí)間復(fù)雜度為O(n^2)朵纷。
// 插入排序
void InsertSort(int arr[], int length)
{
for (int i = 1; i < length; i++)
{
int j;
if (arr[i] < arr[i - 1])
{
int temp = arr[i];
for (j = i - 1; j >= 0 && temp < arr[j]; j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
}
4炭臭、希爾排序
希爾排序(Shell's Sort)在插入排序算法的基礎(chǔ)上進(jìn)行了改進(jìn)，算法的時(shí)間復(fù)雜度與前面幾種算法相比有較大的改進(jìn)袍辞。其算法的基本思想是：先將待排記錄序列分割成為若干子序列分別進(jìn)行插入排序鞋仍，待整個(gè)序列中的記錄"基本有序"時(shí)，再對全體記錄進(jìn)行一次直接插入排序搅吁。
// 插入排序
void ShellSort(int arr[], int length)
{
int increasement = length;
int i, j, k;
do
{
// 確定分組的增量
increasement = increasement / 3 + 1;
for (i = 0; i < increasement; i++)
{
for (j = i + increasement; j < length; j += increasement)
{
if (arr[j] < arr[j - increasement])
{
int temp = arr[j];
for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement)
{
arr[k + increasement] = arr[k];
}
arr[k + increasement] = temp;
}
}
}
} while (increasement > 1);
}
5威创、快速排序
快速排序的基本思想是：通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小谎懦，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序肚豺，已達(dá)到整個(gè)序列有序。一趟快速排序的具體過程可描述為：從待排序列中任意選取一個(gè)記錄(通常選取第一個(gè)記錄)作為基準(zhǔn)值党瓮，然后將記錄中關(guān)鍵字比它小的記錄都安置在它的位置之前详炬，將記錄中關(guān)鍵字比它大的記錄都安置在它的位置之后。這樣寞奸，以該基準(zhǔn)值為分界線呛谜，將待排序列分成的兩個(gè)子序列。
一趟快速排序的具體做法為：設(shè)置兩個(gè)指針low和high分別指向待排序列的開始和結(jié)尾枪萄，記錄下基準(zhǔn)值baseval(待排序列的第一個(gè)記錄)隐岛，然后先從high所指的位置向前搜索直到找到一個(gè)小于baseval的記錄并互相交換，接著從low所指向的位置向后搜索直到找到一個(gè)大于baseval的記錄并互相交換瓷翻，重復(fù)這兩個(gè)步驟直到low=high為止聚凹。
// 快速排序
void QuickSort(int arr[], int start, int end)
{
if (start >= end)
return;
int i = start;
int j = end;
// 基準(zhǔn)數(shù)
int baseval = arr[start];
while (i < j)
{
// 從右向左找比基準(zhǔn)數(shù)小的數(shù)
while (i < j && arr[j] >= baseval)
{
j--;
}
if (i < j)
{
arr[i] = arr[j];
i++;
}
// 從左向右找比基準(zhǔn)數(shù)大的數(shù)
while (i < j && arr[i] < baseval)
{
i++;
}
if (i < j)
{
arr[j] = arr[i];
j--;
}
}
// 把基準(zhǔn)數(shù)放到i的位置
arr[i] = baseval;
// 遞歸
QuickSort(arr, start, i - 1);
QuickSort(arr, i + 1, end);
}
6、歸并排序
“歸并”的含義是將兩個(gè)或兩個(gè)以上的有序序列組合成一個(gè)新的有序表齐帚。假設(shè)初始序列含有n個(gè)記錄妒牙，則可以看成是n個(gè)有序的子序列，每個(gè)子序列的長度為1对妄，然后兩兩歸并湘今，得到（表示不小于x的最小整數(shù)）個(gè)長度為2(或者是1)的有序子序列，再兩兩歸并剪菱。如此重復(fù)摩瞎，直到得到一個(gè)長度為n的有序序列為止拴签。這種排序方法稱為2-路歸并排序。
// 歸并排序
void MergeSort(int arr[], int start, int end, int * temp)
{
if (start >= end)
return;
int mid = (start + end) / 2;
MergeSort(arr, start, mid, temp);
MergeSort(arr, mid + 1, end, temp);
// 合并兩個(gè)有序序列
int length = 0; // 表示輔助空間有多少個(gè)元素
int i_start = start;
int i_end = mid;
int j_start = mid + 1;
int j_end = end;
while (i_start <= i_end && j_start <= j_end)
{
if (arr[i_start] < arr[j_start])
{
temp[length] = arr[i_start];
length++;
i_start++;
}
else
{
temp[length] = arr[j_start];
length++;
j_start++;
}
}
while (i_start <= i_end)
{
temp[length] = arr[i_start];
i_start++;
length++;
}
while (j_start <= j_end)
{
temp[length] = arr[j_start];
length++;
j_start++;
}
// 把輔助空間的數(shù)據(jù)放到原空間
for (int i = 0; i < length; i++)
{
arr[start + i] = temp[i];
}
}
7旗们、堆排序
堆的定義如下: n個(gè)元素的序列{k1, k2, ... , kn}當(dāng)且僅當(dāng)滿足一下條件時(shí)蚓哩，稱之為堆。
可以將堆看做是一個(gè)完全二叉樹上渴。并且岸梨，每個(gè)結(jié)點(diǎn)的值都大于等于其左右孩子結(jié)點(diǎn)的值，稱為大頂堆驰贷；或者每個(gè)結(jié)點(diǎn)的值都小于等于其左右孩子結(jié)點(diǎn)的值盛嘿，稱為小頂堆洛巢。
堆排序(Heap Sort)是利用堆進(jìn)行排序的方法括袒。其基本思想為：將待排序列構(gòu)造成一個(gè)大頂堆(或小頂堆)，整個(gè)序列的最大值(或最小值)就是堆頂?shù)母Y(jié)點(diǎn)稿茉，將根節(jié)點(diǎn)的值和堆數(shù)組的末尾元素交換锹锰，此時(shí)末尾元素就是最大值(或最小值)，然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)堆漓库，這樣就會得到n個(gè)元素中的次大值(或次小值)恃慧，如此反復(fù)執(zhí)行，最終得到一個(gè)有序序列渺蒿。
/*
@param arr 待調(diào)整的數(shù)組
@param i 待調(diào)整的結(jié)點(diǎn)的下標(biāo)
@param length 數(shù)組的長度
*/
void HeapAdjust(int arr[], int i, int length)
{
// 調(diào)整i位置的結(jié)點(diǎn)
// 先保存當(dāng)前結(jié)點(diǎn)的下標(biāo)
int max = i;
// 當(dāng)前結(jié)點(diǎn)左右孩子結(jié)點(diǎn)的下標(biāo)
int lchild = i * 2 + 1;
int rchild = i * 2 + 2;
if (lchild < length && arr[lchild] > arr[max])
{
max = lchild;
}
if (rchild < length && arr[rchild] > arr[max])
{
max = rchild;
}
// 若i處的值比其左右孩子結(jié)點(diǎn)的值小痢士，就將其和最大值進(jìn)行交換
if (max != i)
{
int temp;
temp = arr[i];
arr[i] = arr[max];
arr[max] = temp;
// 遞歸
HeapAdjust(arr, max, length);
}
}
// 堆排序
void HeapSort(int arr[], int length)
{
// 初始化堆
// length / 2 - 1是二叉樹中最后一個(gè)非葉子結(jié)點(diǎn)的序號
for (int i = length / 2 - 1; i >= 0; i--)
{
HeapAdjust(arr, i, length);
}
// 交換堆頂元素和最后一個(gè)元素
for (int i = length - 1; i >= 0; i--)
{
int temp;
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
HeapAdjust(arr, 0, i);
}
}
原文鏈接：https://blog.csdn.net/liang_gu/java/article/details/80627548
