（插入排序氮唯、選擇排序、交換排序姨伟、歸并排序惩琉、基數(shù)排序）
排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序夺荒，而外部排序是因排序的數(shù)據(jù)很大瞒渠，一次不能容納全部的排序記錄，在排序過程中需要訪問外存技扼。
我們這里說說八大排序就是內(nèi)部排序伍玖。
自己用iOS寫了幾個(gè)排序，先來個(gè)數(shù)組：
NSMutableArray *array = [NSMutableArray arrayWithObjects:@89,@2,@22,@95,@88,@66,@43,@31,@57, nil];
1剿吻、直接插入排序
思路：將一個(gè)記錄插入到已排序好的有序表中窍箍，從而得到一個(gè)新，記錄數(shù)增1的有序表丽旅。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列椰棘，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹埂?br>
圖示：
代碼：
-(void)sortingForInsertWithArray:(NSMutableArray *)array{
for (int i = 1; i<=array.count-1; i++) {
int j = i-1;
id temp = array[i];
while (j>=0 && temp<array[j]) {
array[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}
2榄笙、希爾排序
思路：希爾排序是1959 年由D.L.Shell 提出來的邪狞，相對(duì)直接排序有較大的改進(jìn)。希爾排序又叫縮小增量排序茅撞。
先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序帆卓，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序米丘。
圖示：
代碼：
-(void)sortingForShellWithArray:(NSMutableArray *)array{
int dk = (int)(array.count-1)/2;
while (dk>=1) {
[self shellSortingWithArray:array startIndex:dk];
dk = dk/2;
}
}
-(void)shellSortingWithArray:(NSMutableArray *)array startIndex:(int)dk{
for (int i = dk; i<=array.count-1; i+=dk) {
if (array[i]<array[i-dk]) {
int j = i-dk;
id temp = array[i];
array[i] = array[i - dk];
while (j>=0&&temp<array[j]) {
array[j+dk] = array[j];
j-=dk;
}
array[j+dk] = temp;
}
}
}
3鳞疲、簡(jiǎn)單選擇排序
思路：在要排序的一組數(shù)中，選出最腥溲痢（或者最大）的一個(gè)數(shù)與第1個(gè)位置的數(shù)交換尚洽；然后在剩下的數(shù)當(dāng)中再找最小（或者最大）的與第2個(gè)位置的數(shù)交換靶累，依次類推腺毫，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n個(gè)元素（最后一個(gè)數(shù)）比較為止。
圖示：
代碼：
-(void)sortingForSelectWithArray:(NSMutableArray *)array{
int i,j,k;
for (i = 0; i<=array.count-1; i++) {
k = i;
for (j = i+1; j<=array.count-1; j++) {
if (array[k] >array[j] ) {
k = j;
}
}
if (k!=i) {
id temp = array[i];
array[i]= array[k];
array[k]= temp;
}
}
}
4挣柬、堆排序
思路：堆排序是一種樹形選擇排序潮酒，是對(duì)直接選擇排序的有效改進(jìn)。
堆的定義如下：具有n個(gè)元素的序列（k1,k2,...,kn),當(dāng)且僅當(dāng)滿足
（a）大頂堆序列：（96, 83,27,38,11,09)
(b) 小頂堆序列：（12故源，36污抬，24，85绳军，47印机，30，53门驾，91）
初始時(shí)把要排序的n個(gè)數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹（一維數(shù)組存儲(chǔ)二叉樹）射赛，調(diào)整它們的存儲(chǔ)序，使之成為一個(gè)堆奶是，將堆頂元素輸出楣责，得到n 個(gè)元素中最小(或最大)的元素，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最薪胗纭（或者最大）腐魂。然后對(duì)前面(n-1)個(gè)元素重新調(diào)整使之成為堆帐偎，輸出堆頂元素逐纬，得到n 個(gè)元素中次小(或次大)的元素。依此類推削樊，直到只有兩個(gè)節(jié)點(diǎn)的堆豁生，并對(duì)它們作交換，最后得到有n個(gè)節(jié)點(diǎn)的有序序列漫贞。稱這個(gè)過程為堆排序甸箱。
代碼：
-(void)sortingForHeapWithArray:(NSMutableArray *)array{
for (int i = (int)(array.count -1)/2; i>=0; --i) {
[self heapSortingWithArray:array startIndex:i arrayifCount:(int)array.count-1];
}
for (int i = (int)array.count-1; i>0; --i) {
id temp = array[i];
array[i] = array[0];
array[0] = temp;
[self heapSortingWithArray:array startIndex:0 arrayifCount:i];
}
}
-(void)heapSortingWithArray:(NSMutableArray *)array startIndex:(int)startIndex arrayifCount:(int)count{
id temp = array[startIndex];
int child = 2*startIndex +1;
while (child<count) {
if (child+1<count &&array[child]<array[child+1]) {
++child;
}
if (array[startIndex]<array[child]) {
array[startIndex] = array[child];
startIndex = child;
child = 2*startIndex+1;
}else{
break;
}
array[startIndex] = temp;
}
}
5、冒泡排序
思路：在要排序的一組數(shù)中迅脐，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)芍殖，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉谴蔑，較小的往上冒豌骏。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換隐锭。
圖示：
代碼：
-(void)sortingForBubblingWithArray:(NSMutableArray *)array{
for (int i=0; i<=array.count-1; i++) {
for (int j=0; j<array.count-1-i; j++) {
if (array[j] < array[j+1] ) {
id string = array[j];
array[j]= array[j+1];
array[j+1] = string;
}
}
}
}
6窃躲、快速排序
思路：1）選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,
2）通過一趟排序講待排序的記錄分割成獨(dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小钦睡。另一部分記錄的 元素值比基準(zhǔn)值大蒂窒。
3）此時(shí)基準(zhǔn)元素在其排好序后的正確位置
4）然后分別對(duì)這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個(gè)序列有序。
圖示：
a）一趟排序：
b）排序全程：
代碼：
-(void)sortingForFastWithArray:(NSMutableArray *)array strartIndex:(int)strartIndex endIndex:(int)endIndex{
if (strartIndex>endIndex) {
return;
}
int i = strartIndex, j = endIndex;
id key = array[strartIndex];
while (i<j) {
while (i<j && key>=array[j]) {
j--;
}
array[i] = array[j];
while (i<j && key<=array[i]) {
i++;
}
array[j] = array[i];
}
array[i] = key;
[self sortingForFastWithArray:array strartIndex:strartIndex endIndex:i-1];
[self sortingForFastWithArray:array strartIndex:i+1 endIndex:endIndex];
}
7洒琢、歸并排序
思路：歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表秧秉，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的纬凤。然后再把有序子序列合并為整體有序序列福贞。
圖示：
代碼：
-(void)sortingForMergeWithArray:(NSMutableArray *)array standbyArray:(NSMutableArray *)newArray startIndex:(int)startIndex endIndex:(int)endIndex{
int middle;
if (startIndex<endIndex) {
middle = (startIndex +endIndex)/2;
[self sortingForMergeWithArray:array standbyArray:newArray startIndex:startIndex endIndex:middle];
[self sortingForMergeWithArray:array standbyArray:newArray startIndex:middle+1 endIndex:endIndex];
int i = startIndex,
j = middle+1,
k = startIndex;
while (i!=middle+1 && j!=endIndex +1) {
if (array[i]>=array[j]) {
newArray[k++] = array[j++];
}else{
newArray[k++] = array[i++];
}
}
while (i!=middle+1) {
newArray[k++] = array[i++];
}
while (j!=endIndex+1) {
newArray[k++] = array[j++];
}
for (i = startIndex; i<=endIndex; i++) {
array[i] = newArray[i];
}
}
}
