共用方法
/**
交換元素位置
@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;
}