共用方法
/**
交換元素位置
@param element1 元素指針
@param element2 元素指針
*/
void swapElement(int *element1 , int *element2)//交換元素位置
{
int temp = *element1;
*element1 = *element2;
*element2 = temp;
}
/**
打印數(shù)組元素
@param array 排序后的數(shù)組指針
@param count 數(shù)組長(zhǎng)度
*/
void printArray(int *array, int count){
for (int i = 0; i<count; i++) {
NSLog(@"第%d個(gè)元素為 : %d", i, *(array + i));
}
}
1. 插入排序
思路：從數(shù)組中選中目標(biāo)元素(一般從第二個(gè)元素開(kāi)始)敛劝，依次和前面的數(shù)對(duì)比，邊比對(duì)邊移動(dòng)數(shù)據(jù)元素位置绊序，當(dāng)找到合適的位置硕舆，插入目標(biāo)元素≈韫可以想象成整理麻將牌的步驟抚官。
/**
算法 最優(yōu)復(fù)雜度 最差復(fù)雜度 平均復(fù)雜度 穩(wěn)定性 輔助存儲(chǔ)
插入排序 O(n) O(n2) O(n2) 穩(wěn)定 O(1)
@param array 待排序數(shù)組
@param count 數(shù)組長(zhǎng)度
@return 排序后的數(shù)組
*/
int * insertSort(int array[], int count){
for (int i = 1; i<count; i++) {
int j;
int target = array[i];//目標(biāo)元素
for (j = i; j>0 && target<array[j-1]; j--) {//結(jié)束條件
array[j] = array[j-1];//比對(duì)不合適移動(dòng)元素位置
}
array[j] = target;//插入目標(biāo)元素
}
return array;
}
2. shell排序
思路：shell排序是對(duì)插入排序的優(yōu)化，首先對(duì)數(shù)組進(jìn)行跳躍式分組阶捆，一般選擇數(shù)組長(zhǎng)度除以2（即：count/2）得到跳躍的步數(shù)凌节，對(duì)生成的子數(shù)組進(jìn)行排序。每次循環(huán)洒试，步數(shù)/2,結(jié)束條件為步數(shù)<=1;此時(shí)的數(shù)組已經(jīng)大致有序倍奢，最后使用插入排序。
/**
算法 最優(yōu)復(fù)雜度 最差復(fù)雜度 平均復(fù)雜度 穩(wěn)定性 輔助存儲(chǔ)
shell排序O(n^1.3) O(n^1.3) O(n^1.3) 不穩(wěn)定 O(1)
@param array 待排序數(shù)組
@param count 數(shù)組長(zhǎng)度
@return 排序后的數(shù)組
*/
int * shellSort(int array[], int count){
int step = count / 2;
while (step>=1) { //判定結(jié)束條件
for (int i = 0; i<step; i++) {//判定走多少趟
int j = 1;
while (i + step * j < count) {//子數(shù)組的結(jié)束條件
if (array[i + step * (j-1)]>array[i + step * j]) {//交換子數(shù)組位置
swapElement(&array[i + step * (j-1)], &array[i + step * j]);
}
j++;
}
}
step = step / 2;
}
return insertSort(array, count);//調(diào)用插入排序
}
3. 選擇排序
思路：假定第一個(gè)元素為最小元素垒棋，同時(shí)作為目標(biāo)元素卒煞，用目標(biāo)元素和后面的元素進(jìn)行對(duì)比，如果大于捕犬，則記錄索引跷坝，同時(shí)修改目標(biāo)元素酵镜，遍歷結(jié)束也就可以拿到最小值的索引，之后和起始位置的進(jìn)行交換柴钻。
for循環(huán)控制流淮韭，控制跳過(guò)排序過(guò)得元素。
/**
算法 最優(yōu)復(fù)雜度 最差復(fù)雜度 平均復(fù)雜度 穩(wěn)定性 輔助存儲(chǔ)
選擇排序 O(n2) O(n2) O(n2) 不穩(wěn)定 O(1)
@param array 待排序數(shù)組
@param count 數(shù)組長(zhǎng)度
@return 排序后的數(shù)組
*/
int * selectSort(int array[], int count){
for (int i = 0; i < count; i++) {
int index = i;
for (int j = i; j < count-1; j++) {
if (array[j+1]<array[index]) {//設(shè)置哨兵贴届，記錄每次循環(huán)最小的靠粪。思路：默認(rèn)第一個(gè)值為哨兵和后面的數(shù)以此比較，如果小于哨兵毫蚓，記錄索引占键，修改哨兵始終是最小的數(shù)，和后邊的比對(duì)元潘。最后獲取到就是此次遍歷的最小值畔乙，和數(shù)組中的遍歷起始位置交換，從下一個(gè)位置接著下一次循環(huán)翩概，直到跳出循環(huán)牲距，數(shù)組排序結(jié)束，從小到大排序钥庇。
index = j+1;//記錄索引
}
}
swapElement(&array[i], &array[index]);
}
return array;
}
4. 堆排序
思路：堆排序是選擇排序的改進(jìn)算法牍鞠，不再是一步一步選擇，而是根據(jù)二叉樹(shù)的特性评姨，每次篩選子二叉樹(shù)难述。篩選完成時(shí)，將根元素和最后一個(gè)元素交換吐句。之后迭代篩選胁后，每次元素個(gè)數(shù)減一，直到剩余元素為一時(shí)蕴侧，排序完成择同。
/**
算法 最優(yōu)復(fù)雜度 最差復(fù)雜度 平均復(fù)雜度 穩(wěn)定性 輔助存儲(chǔ)
堆排序 O(nlogn) O(nlogn) O(nlogn) 不穩(wěn)定 O(1)
@param array 待排序數(shù)組
@param count 數(shù)組長(zhǎng)度
@return 排序后的數(shù)組
*/
int * heapSort(int array[], int count){
for (int i = count / 2; i > 0; i--) {// 構(gòu)造大頂堆
heapAdjust(array, i, count);
}
for (int i = count - 1; i >= 1; i--) {
swapElement(&array[i], &array[0]); // 交換根結(jié)點(diǎn)與最末節(jié)點(diǎn)
heapAdjust(array, 0, i-1);// 剩余的n-1個(gè)元素再次建立大頂堆
}
return array;
}
void heapAdjust(int array[], int i, int count)
{
int j, temp;
temp = array[i];
j = 2 * i;
while(j <= count-1) {
if (j < count && array[j+1] > array[j]) j++; // 找出較大的子節(jié)點(diǎn)
if (array[j] <= temp) break; // 如果較大的子節(jié)點(diǎn)比父節(jié)點(diǎn)小, 直接返回
array[i] = array[j]; // 設(shè)置父節(jié)點(diǎn)為較大子節(jié)點(diǎn)
i = j; // 記錄調(diào)整后父節(jié)點(diǎn)的位置
j *= 2; // 調(diào)整需要遍歷的子節(jié)點(diǎn)
}
array[i] = temp;
}
5. 冒泡排序
思路：每次比較相鄰的兩個(gè)數(shù)，如果前一個(gè)數(shù)比后一個(gè)數(shù)大净宵，交換兩個(gè)數(shù)的位置，一趟遍歷完成裹纳，大數(shù)已下沉到末尾择葡，下次遍歷只需要遍歷到大數(shù)前一位即可，跳出循環(huán)時(shí)剃氧，已經(jīng)是有序數(shù)組敏储，從小到大。同理也可以從大到小朋鞍。
/**
算法 最優(yōu)復(fù)雜度 最差復(fù)雜度 平均復(fù)雜度 穩(wěn)定性 輔助存儲(chǔ)
冒泡排序 O(n) O(n2) O(n2) 穩(wěn)定 O(1)
@param array 待排序數(shù)組
@param count 數(shù)組長(zhǎng)度
@return 排序后的數(shù)組
*/
int * bubblingSort(int array[], int count){
for (int i = 0; i < count; i++) {//控制多少趟
for (int j = 0; j<count-i-1; j++) {//控制交換次數(shù)
if (array[j]>array[j+1]) {//比較相鄰兩個(gè)元素
swapElement(&array[j+1], &array[j]);//交換元素
}
}
}
return array;
}
6. 快速排序
思路：快速排序是冒泡排序的改進(jìn)算法已添，采用遞歸分治思想妥箕。設(shè)置一個(gè)目標(biāo)元素，建立左右兩個(gè)索引元素更舞，如果目標(biāo)元素是第一個(gè)元素畦幢，從右邊查找，同時(shí)遞減右索引缆蝉，直到遇到比目標(biāo)元素小的值宇葱，和目標(biāo)元素交換，接著和左邊的元素比較刊头，直到遇到大于目標(biāo)元素黍瞧，和目標(biāo)元素交換。也就是目標(biāo)元素依次在左右來(lái)回交換原杂，直到左右索引相同印颤。之后遞歸調(diào)用，設(shè)置一個(gè)邊界條件穿肄，即可完成排序年局。
/**
算法 最優(yōu)復(fù)雜度 最差復(fù)雜度 平均復(fù)雜度 穩(wěn)定性
快速排序 O(n) O(n2) O(logn) 不穩(wěn)定
@param array 待排序數(shù)組
@param left 左邊界
@param right 右邊界
@return 排序后的數(shù)組
*/
int * quickSort(int array[], int left, int right){
if (left>=right) {//遞歸結(jié)束條件
return NULL;
}
int i = left;
int j = right;
int key = array[left];
while (i<j) {//單次排序結(jié)束條件
while (i<j && array[j] >= key) {//小數(shù)向左交換條件
j--;
}
swapElement(&array[i], &array[j]);//交換元素
while (i<j && array[i] <= key) {//大數(shù)向右交換條件
i++;
}
swapElement(&array[i], &array[j]);//交換元素
}
quickSort(array, left, i - 1);//遞歸左分支
quickSort(array, i+1 , right);//遞歸右分支
return array;
}
