一方仿、冒泡排序
1固棚、算法思想
冒泡排序是一種簡單的排序算法，通過循環(huán)遍歷仙蚜，將臨近的兩個(gè)元素進(jìn)行比較此洲，滿足排序規(guī)則時(shí)，進(jìn)行下一組元素對比委粉，當(dāng)不滿足排序規(guī)則時(shí)呜师，將兩個(gè)元素交換位置，再繼續(xù)進(jìn)行下一組元素對比贾节，確保最大的元素在一遍循環(huán)過后一定排在最后面汁汗，然后最后通過最多n2次循環(huán)對比，直到完全有序氮双。
2碰酝、算法描述
![]()
冒泡過程.gif
（1）比較兩個(gè)相鄰的元素霎匈，如果第一個(gè)比第二個(gè)大戴差，那么就交換他們的位置。
（2）重復(fù)步驟（1）的操作铛嘱，依次比較兩兩相鄰的兩個(gè)元素暖释。所有元素對比過后表示一次循環(huán)結(jié)束。
（3）至多循環(huán)n-1次墨吓，重復(fù)上面兩個(gè)步驟球匕。
（4）直到?jīng)]有任何一組元素需要交換位置表示排序完成。
3帖烘、代碼實(shí)現(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亮曹、算法復(fù)雜度
最好的情況為正序，只需要一遍遍歷秘症，所以時(shí)間復(fù)雜度為O(n),最壞的情況為逆序照卦，需要遍歷n2次，所以時(shí)間復(fù)雜度為O(n2)乡摹。由于只有一個(gè)交換的變量temp需要內(nèi)存役耕，所以空間復(fù)雜度為O(1)。
二聪廉、插入排序
1瞬痘、算法思想
將列表中的每個(gè)元素依次和之前排好序的元素進(jìn)行比較故慈，找到合適的位置插入，使之前有序的列表保持依然有序框全。
2察绷、算法描述
![]()
插入排序.gif
（1）從第2個(gè)元素開始，選取第2個(gè)元素（i）津辩，認(rèn)為第1個(gè)元素為一個(gè)只有一個(gè)元素的有序列表克婶。
（2）將選取的元素與之前的元素依次比較，如果選取的元素小于于列表中的元素丹泉，交換他們的位置情萤。
（3）選取下一個(gè)元素（i+1），重復(fù)步驟（2）摹恨，直至列表中的每個(gè)元素都進(jìn)行了步驟（2）的操作筋岛。
3、代碼實(shí)現(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晒哄、算法復(fù)雜度
最好的情況為正序睁宰，只需要一遍遍歷，所以時(shí)間復(fù)雜度為O(n),最壞的情況為逆序寝凌，需要遍歷n2次柒傻，所以時(shí)間復(fù)雜度為O(n2)〗夏荆空間復(fù)雜度為O(1)红符。
三、選擇排序
1伐债、算法思想
從頭開始预侯，遍歷列表找到最小值，把最小的值放在第一個(gè)位置峰锁，在遍歷找到第二小的值放在第一個(gè)后面萎馅，以此類推，知道最后一個(gè)排好序虹蒋。
2糜芳、算法描述
（1）遍歷整個(gè)列表N個(gè)元素，找到最小的元素魄衅，與第一個(gè)元素交換位置峭竣。
（2）遍歷剩余的N-1個(gè)元素，找到最小的元素徐绑，將它排在剩余N-1個(gè)元素的第一個(gè)邪驮。
（3）以此類推，重復(fù)步驟（2）傲茄，直到N-1小于1毅访。
3沮榜、代碼實(shí)現(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、算法復(fù)雜度
不管最后還是最壞的情況喻粹，選擇排序的時(shí)間復(fù)雜度都是O(n2)蟆融，空間復(fù)雜度為O(1)。
四守呜、歸并排序
1型酥、算法思想
歸并排序采用分治的思想，將一個(gè)列表分為多個(gè)子列表查乒，每個(gè)子序列是有序的弥喉。然后再把有序子序列合并為整體有序序列。
2玛迄、算法描述
（1）將列表元素對半分開由境，分為兩個(gè)列表。
（2）重復(fù)步驟（1）蓖议，直至每個(gè)列表只有一個(gè)元素虏杰。
（3）將兩個(gè)相鄰的列表排序，直至真?zhèn)€列表有序勒虾。
3纺阔、代碼實(shí)現(xiàn)
//排序
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex)
{
//i:第一個(gè)待排序的起始位置，
int i = startIndex;
//j:第二個(gè)待排序的起始位置修然，
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++;
}
}
//將兩個(gè)中未排序的添加到tempArr中
while (i != midIndex + 1)
{
tempArr[k] = sourceArr[i];
i++;
k++;
}
//將兩個(gè)中未排序的添加到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笛钝、算法復(fù)雜度
歸并排序是穩(wěn)定排序算法，假設(shè)數(shù)組長度為n低零，那么拆分?jǐn)?shù)組共需logn, 又每步都是一個(gè)普通的合并子數(shù)組的過程婆翔，時(shí)間復(fù)雜度為O(n)拯杠， 故其綜合時(shí)間復(fù)雜度為O(nlogn)掏婶。另一方面， 歸并排序多次遞歸過程中拆分的子數(shù)組需要保存在內(nèi)存空間潭陪， 其空間復(fù)雜度為O(n)雄妥。
五、希爾排序
1依溯、算法思想
希爾排序老厌，也稱遞減增量排序算法。將整個(gè)列表根據(jù)增量分為若干個(gè)子列表分別進(jìn)行插入排序黎炉。隨著增量的減小枝秤，列表趨于基本有序，當(dāng)增量為1時(shí)慷嗜，相當(dāng)再做一次插入排序淀弹，使列表有序丹壕。
2、算法描述
（1）選擇一個(gè)增量gap薇溃，一般為列表長度的一半菌赖。
（2）將列表中元素下標(biāo)每隔gap的元素組成一個(gè)新的子列表。
（3）對每個(gè)子列表進(jìn)行插入排序沐序。
（4）將gap去原來的一半琉用，重復(fù)步驟（2）（3），直到gap小于1策幼。
3邑时、代碼實(shí)現(xiàn)
void ShellSort(int* slist, int length)
{
int temp;
//gap為增量，一般取長度的一般
int gap = length / 2;
//當(dāng)增量小于1時(shí)結(jié)束排序
while (gap >= 1)
{
//最多分為gap個(gè)列表
for (int i = 0; i < gap; i++)
{
//下面的代碼為一個(gè)簡單的插入排序特姐，只是插入排序的數(shù)組下標(biāo)每次移動(dòng)的不是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刁愿、算法復(fù)雜度
希爾排序是不穩(wěn)定的排序，它時(shí)間復(fù)雜度和步長的選擇有關(guān)到逊。
看如下兩個(gè)增量序列：
n/2铣口、n/4、n/8...1
1觉壶、3脑题、7...2^k-1
第一個(gè)序列稱為希爾增量序列，使用希爾增量時(shí)铜靶，希爾排序在最壞情況下的時(shí)間復(fù)雜度為O(n2)叔遂。
第二個(gè)序列稱為Hibbard增量序列，使用Hibbard增量時(shí)争剿，希爾排序在最壞情況下的時(shí)間復(fù)雜度為O(n3/2)已艰。
六、快速排序
1蚕苇、算法思想
快速排序采用分治的思想哩掺，通通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小涩笤，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序嚼吞，整個(gè)排序過程可以 遞歸 進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列蹬碧。
2舱禽、算法描述
（1）選定一個(gè)基準(zhǔn)元素
（2）從右往左找到比基準(zhǔn)元素小的元素
（3）從左往右找到比基準(zhǔn)元素大的元素
（4）交換左右找到的兩個(gè)元素的位置
（5）重復(fù)上面（2）（3）（4）步，直至左右兩個(gè)元素相遇恩沽。
3誊稚、代碼實(shí)現(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;
//直到遍歷完整個(gè)列表
while (i < j)
{
//從右到左找到小于key的下標(biāo)
while (i<j&&slist[j] >= key)
{
j--;
}
//從左到右找到大于key的下標(biāo)
while (i<j && slist[i] <= key)
{
i++;
}
//交換找到的兩個(gè)元素,保證小的元素在前，大的元素在后
if (i < j)
{
temp = slist[i];
slist[i] = slist[j];
slist[j] = temp;
}
}
//將key元素交換到中間，確保分為大小兩個(gè)列表
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++)
{
//遍歷整個(gè)列表里伯，找到小于key的元素個(gè)數(shù)绽昏，并且通過交換位置，讓他們的下標(biāo)都在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]的兩個(gè)列表
slist[right] = slist[j + 1];
slist[j + 1] = key;
QuickSort2(slist,left,j);
QuickSort2(slist, j+2, right);
}
4全谤、算法復(fù)雜度
快速排序之所比較快，因?yàn)橄啾让芭菖判蛞叮看谓粨Q是跳躍式的认然。每次排序的時(shí)候設(shè)置一個(gè)基準(zhǔn)點(diǎn)，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊漫萄，將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的右邊卷员。這樣在每次交換的時(shí)候就不會(huì)像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換，交換的距離就大的多了腾务。因此總的比較和交換次數(shù)就少了毕骡，速度自然就提高了。當(dāng)然在最壞的情況下岩瘦，仍可能是相鄰的兩個(gè)數(shù)進(jìn)行了交換未巫。因此快速排序的最差時(shí)間復(fù)雜度和冒泡排序是一樣的都是O(N2)，它的平均時(shí)間復(fù)雜度為O(NlogN)启昧。
