一、冒泡排序
1、算法思想
冒泡排序是一種簡單的排序算法，通過循環(huán)遍歷，將臨近的兩個元素進行比較，滿足排序規(guī)則時，進行下一組元素對比，當不滿足排序規(guī)則時，將兩個元素交換位置，再繼續(xù)進行下一組元素對比，確保最大的元素在一遍循環(huán)過后一定排在最后面，然后最后通過最多n2次循環(huán)對比，直到完全有序。
2、算法描述
![]()
冒泡過程.gif
（1）比較兩個相鄰的元素，如果第一個比第二個大，那么就交換他們的位置。
（2）重復步驟（1）的操作，依次比較兩兩相鄰的兩個元素。所有元素對比過后表示一次循環(huán)結(jié)束。
（3）至多循環(huán)n-1次，重復上面兩個步驟。
（4）直到?jīng)]有任何一組元素需要交換位置表示排序完成。
3、代碼實現(xiàn)
void BubbleSort(int* slist,int length)
{
int temp;
for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - 1 - i; j++)
{
if (slist[j] > slist[j + 1])
{
temp = slist[j];
slist[j] = slist[j + 1];
slist[j + 1] = temp;
}
}
}
}
int main()
{
int sortlist[] = { 5,0,4,1,8,3,7 };
BubbleSort(sortlist,7);
}
4、算法復雜度
最好的情況為正序，只需要一遍遍歷，所以時間復雜度為O(n),最壞的情況為逆序，需要遍歷n2次，所以時間復雜度為O(n2)。由于只有一個交換的變量temp需要內(nèi)存，所以空間復雜度為O(1)。
二、插入排序
1、算法思想
將列表中的每個元素依次和之前排好序的元素進行比較，找到合適的位置插入，使之前有序的列表保持依然有序。
2、算法描述
![]()
插入排序.gif
（1）從第2個元素開始，選取第2個元素（i），認為第1個元素為一個只有一個元素的有序列表。
（2）將選取的元素與之前的元素依次比較，如果選取的元素小于于列表中的元素，交換他們的位置。
（3）選取下一個元素（i+1），重復步驟（2），直至列表中的每個元素都進行了步驟（2）的操作。
3、代碼實現(xiàn)
//方法一
void InsertSort1(int* slist,int length)
{
int temp;
for (int i = 1; i < length; i++)
{
int j = i -1;
while (slist[j] > slist[j+1] && j >= 0)
{
//交換位置
temp = slist[j];
slist[j] = slist[j+1];
slist[j+1] = temp;
j--;
/*或者這樣交換*/
// slist[j+1] = slist[j] + slist[j+1];
// slist[j] = slist[j+1] - slist[j];
// slist[j+1] = slist[j+1] - slist[j];
// j--;
}
}
}
//方法二
void InsertSort2(int* slist,int length)
{
for (int i = 1; i < length; i++)
{
int j = i - 1;
int number = slist[i];
while (j >= 0 && slist[j] > number)
{
slist[j+1] = slist[j];
j--;
}
slist[j+1] = number;
}
}
4、算法復雜度
最好的情況為正序，只需要一遍遍歷，所以時間復雜度為O(n),最壞的情況為逆序，需要遍歷n2次，所以時間復雜度為O(n2)?？臻g復雜度為O(1)。
三、選擇排序
1、算法思想
從頭開始，遍歷列表找到最小值，把最小的值放在第一個位置，在遍歷找到第二小的值放在第一個后面，以此類推，知道最后一個排好序。
2、算法描述
（1）遍歷整個列表N個元素，找到最小的元素，與第一個元素交換位置。
（2）遍歷剩余的N-1個元素，找到最小的元素，將它排在剩余N-1個元素的第一個。
（3）以此類推，重復步驟（2），直到N-1小于1。
3、代碼實現(xiàn)
void SelectSort(int* slist, int length)
{
int min;
int temp;
for (int i = 0; i < length; i++)
{
min = i;
for (int j = i + 1; j < length; j++)
{
if (slist[j] < slist[min])
{
min = j;
}
}
temp = slist[i];
slist[i] = slist[min];
slist[min] = temp;
}
}
4、算法復雜度
不管最后還是最壞的情況，選擇排序的時間復雜度都是O(n2)，空間復雜度為O(1)。
四、歸并排序
1、算法思想
歸并排序采用分治的思想，將一個列表分為多個子列表，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
2、算法描述
（1）將列表元素對半分開，分為兩個列表。
（2）重復步驟（1），直至每個列表只有一個元素。
（3）將兩個相鄰的列表排序，直至真?zhèn)€列表有序。
3、代碼實現(xiàn)
//排序
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex)
{
//i:第一個待排序的起始位置，
int i = startIndex;
//j:第二個待排序的起始位置，
int j = midIndex + 1;
int k = startIndex;
while (i != midIndex + 1 && j != endIndex+1)
{
if (sourceArr[i] > sourceArr[j])
{
tempArr[k] = sourceArr[j];
k++;
j++;
}
else
{
tempArr[k] = sourceArr[i];
k++;
i++;
}
}
//將兩個中未排序的添加到tempArr中
while (i != midIndex + 1)
{
tempArr[k] = sourceArr[i];
i++;
k++;
}
//將兩個中未排序的添加到tempArr中
while (j != endIndex+1)
{
tempArr[k] = sourceArr[j];
j++;
k++;
}
//將tempArr中的元素賦值給sourceArr
for (int i = startIndex; i <= endIndex; i++)
{
sourceArr[i] = tempArr[i];
}
}
//分解遞歸
void BranchSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
if (startIndex < endIndex)
{
int mid = startIndex + (endIndex - startIndex) / 2;
BranchSort(sourceArr, tempArr, startIndex, mid);
BranchSort(sourceArr, tempArr, mid+1, endIndex);
MergeSort(sourceArr, tempArr, startIndex, mid, endIndex);
}
}
4、算法復雜度
歸并排序是穩(wěn)定排序算法，假設數(shù)組長度為n，那么拆分數(shù)組共需logn, 又每步都是一個普通的合并子數(shù)組的過程，時間復雜度為O(n)， 故其綜合時間復雜度為O(nlogn)。另一方面， 歸并排序多次遞歸過程中拆分的子數(shù)組需要保存在內(nèi)存空間， 其空間復雜度為O(n)。
五、希爾排序
1、算法思想
希爾排序，也稱遞減增量排序算法。將整個列表根據(jù)增量分為若干個子列表分別進行插入排序。隨著增量的減小，列表趨于基本有序，當增量為1時，相當再做一次插入排序，使列表有序。
2、算法描述
（1）選擇一個增量gap，一般為列表長度的一半。
（2）將列表中元素下標每隔gap的元素組成一個新的子列表。
（3）對每個子列表進行插入排序。
（4）將gap去原來的一半，重復步驟（2）（3），直到gap小于1。
3、代碼實現(xiàn)
void ShellSort(int* slist, int length)
{
int temp;
//gap為增量，一般取長度的一般
int gap = length / 2;
//當增量小于1時結(jié)束排序
while (gap >= 1)
{
//最多分為gap個列表
for (int i = 0; i < gap; i++)
{
//下面的代碼為一個簡單的插入排序，只是插入排序的數(shù)組下標每次移動的不是1而是gap
for (int j = i+gap; j < length; j = j + gap)
{
if (slist[j] < slist[j-gap])
{
int k = j - gap;
int temp = slist[j];
while (k >= 0 && slist[k] > temp)
{
slist[k + gap] = slist[k];
k = k - gap;
}
slist[k+gap] = temp;
}
}
}
//增量遞減
gap = gap/ 2;
}
}
4、算法復雜度
希爾排序是不穩(wěn)定的排序，它時間復雜度和步長的選擇有關。
看如下兩個增量序列：
n/2、n/4、n/8...1
1、3、7...2^k-1
第一個序列稱為希爾增量序列，使用希爾增量時，希爾排序在最壞情況下的時間復雜度為O(n2)。
第二個序列稱為Hibbard增量序列，使用Hibbard增量時，希爾排序在最壞情況下的時間復雜度為O(n3/2)。
六、快速排序
1、算法思想
快速排序采用分治的思想，通通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以 遞歸 進行，以此達到整個數(shù)據(jù)變成有序序列。
2、算法描述
（1）選定一個基準元素
（2）從右往左找到比基準元素小的元素
（3）從左往右找到比基準元素大的元素
（4）交換左右找到的兩個元素的位置
（5）重復上面（2）（3）（4）步，直至左右兩個元素相遇。
3、代碼實現(xiàn)
void QuickSort(int* slist, int left, int right)
{
if (left >= right)
{
return;
}
int i = left;
int j = right;
int key = slist[left];
int temp;
//直到遍歷完整個列表
while (i < j)
{
//從右到左找到小于key的下標
while (i<j&&slist[j] >= key)
{
j--;
}
//從左到右找到大于key的下標
while (i<j && slist[i] <= key)
{
i++;
}
//交換找到的兩個元素,保證小的元素在前，大的元素在后
if (i < j)
{
temp = slist[i];
slist[i] = slist[j];
slist[j] = temp;
}
}
//將key元素交換到中間，確保分為大小兩個列表
temp = slist[left];
slist[left] = slist[j];
slist[j] = temp;
QuickSort(slist, left, j - 1);
QuickSort(slist, j + 1, right);
}
void QuickSort2(int* slist, int left, int right)
{
if (left >= right)
{
return;
}
int j = left-1;
int key = slist[right];
int temp;
for (int i = left; i < right; i++)
{
//遍歷整個列表，找到小于key的元素個數(shù)，并且通過交換位置，讓他們的下標都在j的前面
if (slist[i] < key)
{
j++;
if (i != j)
{
temp = slist[i];
slist[i] = slist[j];
slist[j] = temp;
}
}
}
//將key的位置與j+1的位置互換，保證將slist列表分為小于slist[j+1]與大于slist[j+1]的兩個列表
slist[right] = slist[j + 1];
slist[j + 1] = key;
QuickSort2(slist,left,j);
QuickSort2(slist, j+2, right);
}
4、算法復雜度
快速排序之所比較快，因為相比冒泡排序，每次交換是跳躍式的。每次排序的時候設置一個基準點，將小于等于基準點的數(shù)全部放到基準點的左邊，將大于等于基準點的數(shù)全部放到基準點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數(shù)之間進行交換，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了，速度自然就提高了。當然在最壞的情況下，仍可能是相鄰的兩個數(shù)進行了交換。因此快速排序的最差時間復雜度和冒泡排序是一樣的都是O(N2)，它的平均時間復雜度為O(NlogN)。
