首先看一下排序的定義：
排序轨功，就是重新排列表中的元素汗茄，使表中的元素滿(mǎn)足按關(guān)鍵字遞增或遞減的過(guò)程彩掐。為了查找方便，通常需要計(jì)算機(jī)中的表示按關(guān)鍵字有序的枫匾。
接著是算法的穩(wěn)定性：
若待排序表中有兩個(gè)元素Ri和Rj架诞，其對(duì)應(yīng)的關(guān)鍵字keyi=keyj，且在排序前Ri在Rj前面干茉，若使用某一排序算法后谴忧，Ri仍然在Rj前面，則稱(chēng)這個(gè)排序算法是穩(wěn)定的角虫，否則稱(chēng)這個(gè)排序算法是不穩(wěn)定的沾谓。需要注意的是，算法是否具有穩(wěn)定性并不能衡量一個(gè)算法的優(yōu)劣戳鹅，它主要是對(duì)算法的性質(zhì)進(jìn)行描述均驶。
一、插入排序
插入排序是一種簡(jiǎn)單直觀的排序方法枫虏，其基本思想是每次將一個(gè)待排序的記錄按其關(guān)鍵字大小插到前面已排好的子序列中妇穴，直到全部記錄插入完成。
由插入排序的思想可以引申出三個(gè)重要的排序算法：直接插入排序隶债、折半插入排序和希爾排序腾它。
1、直接插入排序
簡(jiǎn)單粗暴的代碼先上??
void insert_sort(int s[]) {
int temp = 0;
for (int i = 1; i < s.length; i++) {
if (s[i] < s[i - 1]) {
temp = s[i];
while(i>0 && temp<s[i-1]){
s[i]=s[i-1];
i--;
}
s[i]=temp;
}
}
}
空間復(fù)雜度O(1)死讹，時(shí)間復(fù)雜度為O(n2)瞒滴，是一個(gè)穩(wěn)定排序方法，適用于順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的線性表赞警。
2逛腿、折半插入排序
折半插入排序（Binary Insertion Sort）是對(duì)插入排序算法的一種改進(jìn)，所謂排序算法過(guò)程仅颇，就是不斷的依次將元素插入前面已排好序的序列中单默。
排序思想：有一組數(shù)據(jù)待排序，排序區(qū)間為Array[0] ~ Array[n-1]忘瓦。將數(shù)據(jù)分為有序數(shù)據(jù)和無(wú)序數(shù)據(jù)搁廓，第一次排序時(shí)默認(rèn)Array[0]為有序數(shù)據(jù)引颈，Array[1] ~ Array[n-1]為無(wú)序數(shù)據(jù)。有序數(shù)據(jù)分區(qū)的第一個(gè)元素位置為low境蜕，最后一個(gè)元素的位置為high蝙场。
遍歷無(wú)序區(qū)間的所有元素，每次取無(wú)序區(qū)間的第一個(gè)元素Array[i]粱年，因?yàn)? ~ i-1是有序排列的售滤，所以用中點(diǎn)m將其平分為兩部分，然后將待排序數(shù)據(jù)同中間位置為m的數(shù)據(jù)進(jìn)行比較台诗，若待排序數(shù)據(jù)較大完箩，則low~m-1分區(qū)的數(shù)據(jù)都比待排序數(shù)據(jù)小，反之拉队，若待排序數(shù)據(jù)較小弊知，則m+1 ~ high分區(qū)的數(shù)據(jù)都比 待排序數(shù)據(jù)大，此時(shí)將low或high重新定義為新的合適分區(qū)的邊界粱快，對(duì)新的小分區(qū)重復(fù)上面操作秩彤。直到low和high 的前后順序改變，此時(shí)high+1所處位置為待排序數(shù)據(jù)的合適位置事哭。
下面是代碼：
void half_insert_sort(int s[]) {
int i,j,low,high,mid;
int temp;
for (i = 1; i < s.length; i++) {
temp = s[i];
low = 0;
high = i-1;
while (low <= high) {
mid = (low + high) / 2;
if(s[mid]>temp) high = mid - 1;
else low = mid + 1;
}
for (j = i - 1; j >= high + 1; --j) s[j + 1] = s[j];
s[high+1]=temp;
}
}
折半插入排序僅減少了比較元素的次數(shù)漫雷，約為O(nlog2n)，時(shí)間復(fù)雜度O(n2)鳍咱，空間復(fù)雜度O(1)降盹，是一個(gè)穩(wěn)定排序方法。
3流炕、希爾排序
希爾排序的基本思想是：先將排序表分割成若干形如L[i,i+d,i+2d,...,i+kd]的“特殊”子表，分別進(jìn)行插入排序仅胞，當(dāng)整個(gè)表中的元素已呈“基本有序”時(shí)每辟，再對(duì)全體記錄進(jìn)行一次直接插入排序。
代碼如下：
void ShellSort(int s[]) {
int n = s.length;
int dk;
int temp;
int i,j;
for (dk = n / 2; dk >= 1; dk = dk / 2) {
for (i = dk; i < n; i++) {
if(s[i]<s[i-dk]){
temp = s[i];
for (j = i - dk; j >=0 && temp<=s[j]; j -= dk) {
s[j+dk]=s[j];
}
s[j+dk]=temp;
}
}
}
}
該算法空間復(fù)雜度O(1)干旧，時(shí)間復(fù)雜度O(n2)渠欺，不穩(wěn)定，僅適用于線性表為順序存儲(chǔ)的情況椎眯。
二挠将、交換排序
所謂交換，是指根據(jù)序列中兩個(gè)關(guān)鍵字的比較結(jié)果來(lái)對(duì)換這兩個(gè)記錄在序列中的位置编整，基于交換的排序算法很多舔稀，主要有冒泡排序和快速排序。
1掌测、冒泡排序
冒泡排序的基本思想是：假設(shè)待排序表長(zhǎng)為n内贮，從后往前（或從前往后）兩兩比較相鄰元素的值，若為逆序（即A[i-1]>A[i]），則交換他們夜郁，直到序列比較完什燕。我們稱(chēng)它為一趟冒泡，結(jié)果是將最小的元素交換到待排序列的第一個(gè)位置竞端。下一趟排列時(shí)屎即，前一趟確定的最小元素不再參加比較，待排序列減少一個(gè)元素事富，每趟冒泡的結(jié)果就是把序列中的最小元素放到了最終的位置技俐，這樣最多做n-1趟冒泡就能把所有元素排好序。
算法代碼如下：
void BubbleSort(int s[]) {
int temp;
for(int i=0;i<s.length-1;i++){ //遍歷數(shù)組長(zhǎng)度的次數(shù)
for(int j=0;j<s.length-i-1;j++){
if(s[j]>s[j+1]){
temp=s[j];
s[j]=s[j+1];
s[j+1]=temp;
}
}
}
} //向后冒泡
void Bubble(int s[]) {
int temp;
for (int i = 0; i < s.length-1; i++) {
for(int j=s.length-1;j>i;j--){
if(s[j]<s[j-1]){
temp = s[j];
s[j] = s[j - 1];
s[j - 1] = temp;
}
}
}
} //向前冒泡
以上包含了向前冒泡和向后冒泡赵颅∷淞恚空間復(fù)雜度為O(1)，時(shí)間復(fù)雜度為O(n2)饺谬，是一種穩(wěn)定的排序方法捂刺。
2、快速排序
快速排序是很重要的排序方法募寨，面試中經(jīng)常會(huì)問(wèn)族展。快速排序是對(duì)冒泡排序的一種改進(jìn)拔鹰，其基本思想是分治仪缸，更多詳細(xì)內(nèi)容請(qǐng)戳：https://www.runoob.com/w3cnote/quick-sort.html
下面是實(shí)現(xiàn)代碼：
void quick_sort(int s[], int low, int high)
{
if (low < high)
{
int i = low, j = high, x = s[low];
while (i < j)
{
while(i < j && s[j] >= x) // 從右向左找第一個(gè)小于x的數(shù)
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) // 從左向右找第一個(gè)大于等于x的數(shù)
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, low, i - 1); // 遞歸調(diào)用
quick_sort(s, i + 1, high);
}
}
對(duì)算法的最好理解方式是手動(dòng)地模擬一遍這些算法
該算法空間復(fù)雜度最壞情況下是O(n)，在平均情況下是O(log2n)列肢，時(shí)間復(fù)雜度為O(n2)恰画，是一個(gè)不穩(wěn)定的排序方法。
注：在快速排序算法中瓷马，并不產(chǎn)生有序子序列拴还，但每趟排序后悔將一個(gè)元素（基準(zhǔn)元素）放到其最終的位置上。
