排序算法
- 冒泡排序
- 選擇排序
- 直接插入排序
- 希爾排序
- 堆排序
- 歸并排序
- 快速排序
-計(jì)數(shù)排序
冒泡排序
冒泡排序是一種交換排序搭独，基本思想是兩兩相鄰的記錄的關(guān)鍵字摊聋，如果反序則交換，知道沒有反序?yàn)橹埂?/p>
冒泡排序的復(fù)雜度是n(n-1)/2,就是o(n2)鞠鲜。
/*對順序列表排序*/
-(void)sort:(NSMutableArray *)list{
NSInteger i , j;
for (i = 0; i < list.count; i ++) {
for (j = list.count-1; j>=i; j --) {
if (list[j] > list[i]) {
/*
交換obj
*/
[list exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
}
選擇排序
簡單選擇排序法是通過n-i次關(guān)鍵字間的比較，從n-i+1個(gè)記錄選出關(guān)鍵字最小的記錄断国，并和第i（1=《i《=n）交換之贤姆。
選擇排序復(fù)雜度是n（n-1）/2,就是o（n2），性能略優(yōu)于冒泡稳衬。
-(void)sort:(NSMutableArray *)list{
NSInteger i , j , min;
for (i = 1; i < list.count; i ++) {
min = i; //默認(rèn)最小值是第一個(gè)
for (j = i + 1; j <= list.count; j ++) {
if (list[min] > list[j] ) {
min = j; //記錄最小值的索引
}
}
if (min != i) {// 出現(xiàn)最小的值的時(shí)候 和上個(gè)最小的值交換位置
/*
交換obj
*/
[list exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
直接插入排序算法
直接插入排序的基本操作是將一個(gè)記錄插入到已經(jīng)排好的有序表中霞捡，從而得到一個(gè)新的，記錄增加1的有序表薄疚。
直接插入排序時(shí)間復(fù)雜度是（n+4）（n-1）/2碧信，就是o（n2）赊琳。
性能略優(yōu)于選擇排序。
-(void)sort2:(NSMutableArray *)list{
NSInteger i , j ;
for (i = 1; i < list.count; i ++) {
if (list[i-1] < list[i]) {// i-1 小于 i
NSInteger data = [list[i] integerValue];//設(shè)置哨兵
for (j = i - 1; j >= 0 && [list[j] integerValue] < data ; j --) {
list[j+1] = list[j];//向后移動(dòng)一位
}
if (data) {
list[j+1] =@(data);//哨兵賦值
}
}
}
}
希爾排序
希爾排序是把記錄按下標(biāo)的一定增量分組砰碴，對每組使用直接插入排序算法排序躏筏；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多呈枉，當(dāng)增量減至1時(shí)趁尼，整個(gè)文件恰被分成一組，算法便終止猖辫。
//希爾排序算法
-(void)shellSort:(NSMutableArray *)list{
NSInteger i , j ;
NSInteger inrement = list.count;
do {
inrement = inrement/3 + 1;//增量序列
for (i = inrement+1; i < list.count; i ++) {
if (list[i]<list[i-inrement]) {
//需將list[i] 插入有序增量字表
NSNumber * data = list[i];
for (j = i - inrement; j >0 && data < list[j]; j-= inrement) {
list[j+inrement] = list[j];//記錄后移
}
list[j+inrement] = data;//插入
}
}
}while (inrement > 1);
}
希爾排序和直接插入排序有異曲同工之妙酥泞，都是記錄后移，都是插入排序啃憎。不過希爾用的條件是步長婶博，步長越來越短，直到是1荧飞，而直接插入排序是直接是1凡人，循環(huán)次數(shù)多。
時(shí)間復(fù)雜度是o(n的二分之三次方)叹阔，優(yōu)于o（n2）挠轴。
堆排序
基本思想是將帶排序的序列構(gòu)造成一個(gè)大堆，此時(shí)耳幢，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)岸晦。將他移走（其實(shí)是將其與堆數(shù)組的末尾元素交換，此時(shí)末尾元素就是最大值）睛藻，然后將剩余的n-1個(gè)序重新構(gòu)造一個(gè)堆启上，這樣會得到n個(gè)元素中的次小值。如此反復(fù)店印，便能得到一個(gè)有序序列了冈在。
程序暫沒有,后期完善。
歸并排序
原理是利用初始序列含有n個(gè)記錄按摘，則可以看成n個(gè)有序的子序列包券，每個(gè)子序列的長度為1，然后兩兩歸并炫贤，得到【n/2】（【x】表示不小于x的最小整數(shù)）個(gè)長度為2 或1的有序子列溅固，然后兩兩歸并，兰珍。侍郭。。。如此重復(fù)亮元，直至得到一個(gè)長度為n的有序序列汰寓，這種排發(fā)稱為2路歸并排序。
程序暫沒有,后期完善苹粟。
快速排序
基本思想是:通過一趟排序?qū)判蛴涗浄指畛瑟?dú)立的兩部分有滑，其中一部分記錄的關(guān)鍵字均比另外一部分的關(guān)鍵字小，則可分別對著兩部分重新排序嵌削，以達(dá)到整個(gè)序列的有序的目的毛好。
// 快速排序
-(void)quickSort:(NSMutableArray *)list{
[self qsort:list low:0 hight:list.count-1];
}
-(void)qsort:(NSMutableArray *)list low:(NSInteger)low hight:(NSInteger ) hight{
NSInteger pt;
if (low < hight) {
pt =[self partition:list low:low high:hight];//將整個(gè)序列一分為二
[self qsort:list low:low hight:pt -1];//對低子表遞歸排序
[self qsort:list low:pt + 1 hight:hight];//對高字表遞歸排序
}
}
//返回在他前后記錄均不大（小）與他苛秕。
-(NSInteger)partition:(NSMutableArray *)list low:(NSInteger)low high:(NSInteger)high{
NSNumber * data = list[low];
while (low < high) {
while (low < high && list[high] >= data)// 倒敘 找出比data小的 并交換位置
high --;
[list exchangeObjectAtIndex:low withObjectAtIndex:high];
while (low < high && list[low] <= data)//正序 找出比data大的 并交換位置
low ++;
[list exchangeObjectAtIndex:low withObjectAtIndex:high];
}
return low;
}
時(shí)間復(fù)雜度是o（n2）空間復(fù)雜度是o（log n）肌访。
優(yōu)化選擇樞軸
三數(shù)取中發(fā)，就是取三個(gè)關(guān)鍵字排序艇劫，將中間的數(shù)作為樞軸吼驶，一般是取左，右店煞，中間三個(gè)數(shù)蟹演。
data = list[low];
將上面的一行改成下邊的：
NSNumber * data;
NSInteger m = low + (high + low)/2;
if (list[low] > list[high]) {
[list exchangeObjectAtIndex:low withObjectAtIndex:high];
}
if (list[m] > list[high]) {
[list exchangeObjectAtIndex:m withObjectAtIndex:high];
}
if (list[m] > list[low]) {
[list exchangeObjectAtIndex:m withObjectAtIndex:low];
}
data = list[low];
優(yōu)化不必要的交換
//返回在他前后記錄均不大（小）與他顷蟀。
-(NSInteger)partition:(NSMutableArray *)list low:(NSInteger)low high:(NSInteger)high{
NSNumber * data;
NSInteger m = low + (high - low)/2;
if (list[low] > list[high]) {
[list exchangeObjectAtIndex:low withObjectAtIndex:high];
}
if (list[m] > list[high]) {
[list exchangeObjectAtIndex:m withObjectAtIndex:high];
}
if (list[m] > list[low]) {
[list exchangeObjectAtIndex:m withObjectAtIndex:low];
}
data = list[low];//取出來適當(dāng)?shù)年P(guān)鍵字
while (low < high) {
while (low < high && list[high] >= data)// 倒敘 找出比data小的 并交換位置
high --;
list[low] = list[high]; //將 上面的交換改成直接賦值
while (low < high && list[low] <= data)//正序 找出比data大的 并交換位置
low ++;
list[high ] = list[low]; //將 上面的交換改成直接賦值
}
list[low] = data; //最后 將關(guān)鍵字 賦值給low的位置
return low;
}
歸并排序和堆排序暫時(shí)沒有完善酒请，下一期將完善。
計(jì)數(shù)排序
缺點(diǎn)是整數(shù)型的好牌鸣个，小數(shù)點(diǎn)的要轉(zhuǎn)化成整數(shù)再排序羞反。時(shí)間負(fù)責(zé)度0(n+k)，空間復(fù)雜度是o(n+k),性能優(yōu)于所有比較排序算法囤萤。
func countsSort(list:inout [Int],n:Int) -> Void{
let startTime1 = CFAbsoluteTimeGetCurrent();
var dic = [Int:Int]();
//key value 存儲數(shù)組都讀取到dic 中
for index in 0..<n {
let item = list[index];
var value:Int = dic[item] ?? 0;
value += 1;
dic[item] = value;
}
//刪除所有的舊數(shù)組
list.removeAll();
//根據(jù)dic 中組裝成新的array
for index in 0..<n {
let item = index;
var value:Int = dic[item] ?? 0;
while value > 0 {
list.append(index);
value -= 1;
}
}
let endTime1 = CFAbsoluteTimeGetCurrent();
let timeCount1 = (endTime1 - startTime1);
print("countsSorttime:\(timeCount1)s");
}
