記錄一下常用的算法吉殃， 方便以后復(fù)習(xí)或者查閱衰琐， 有的還需要優(yōu)化
1.冒泡算法
主要思路就是從數(shù)組的最后面的元素開始比較宏娄，前面一個元素比后面一個元素要大的話毙石， 就交換位置廉沮。 采用一個Falg標(biāo)志位是為了優(yōu)化算法， 因為有可能冒泡交換一定次數(shù)的時候數(shù)組就已經(jīng)是按順序排序了徐矩， 所以就可以停止循環(huán)了
時間復(fù)雜度最好是O(n), 最差是O(n * n)
-(void)BubbleSort {
NSMutableArray *array = [NSMutableArray arrayWithObjects:@2,@4,@5,@1,@9,@7,@6,@8,@3, nil];
BOOL flag = YES;
// NSNumber *temp = nil;
int count = (int)array.count;// NSUInteger 轉(zhuǎn)化為 int 滞时，要不有問題
for (int i = 0; i < count && flag; i++) {
flag = NO;
for (int j = (count - 2); j >= i; j--) {
NSLog(@"%zd--%zd\n", i, j);
if (array[j] > array[j + 1]) {
// temp = array[j];
// array[j] = array[j + 1];
// array[j + 1] = temp;
[array exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
flag = YES;//來到這里證明還是要交換的，直到不進(jìn)這里說明已經(jīng)排好序了滤灯， 后面就不用繼續(xù)遍歷比較了
NSLog(@"%@", array);
}
}
}
}
2.選擇排序
主要思路就是：把當(dāng)前元素當(dāng)做最小的元素坪稽，跟數(shù)組里面自己位置后面的每一個元素比較，如果比自己小力喷，則記錄最小元素的下標(biāo)刽漂， 比較完畢后， 當(dāng)前元素元素和最小元素的位置交換弟孟。
時間復(fù)雜度是O(n * n)贝咙，性能比冒泡算法要好
-(void)simpleSelectionSort {
NSMutableArray *array = [NSMutableArray arrayWithObjects:@2,@4,@5,@1,@9,@7,@6,@8,@3, nil];
int count = (int)array.count;// NSUInteger 轉(zhuǎn)化為 int ，要不有問題
int min;
for (int i = 0 ; i < count; i++) {
min = i;
for (int j = i + 1; j < count; j++) {
if (array[min] > array[j]) {
min = j;
}
}
if (min != i) {
// NSNumber *temp = array[min];
// array[min] = array[i];
// array[i] = temp;
[array exchangeObjectAtIndex:min withObjectAtIndex:i];
}
}
NSLog(@"%@", array);
}
3.直接插入算法
直接插入算法：將一個記錄插入到已經(jīng)排好序的有序表中拂募， 從而得到一個新的庭猩， 記錄數(shù)增1 的有序表窟她；
本例中： 2， 4蔼水， 5震糖， 中已經(jīng)排好序了， 接下來的 1 要插入到第一個位置趴腋，先記錄1所在位置的數(shù)值1吊说， 然后 5，4优炬，2颁井，按順序往后挪動一個位置， 1 的位置 變成5蠢护， 5的位置變成4雅宾， 4 的位置變成2， 然后再把之前記錄1所在位置的數(shù)值1賦值到?jīng)]挪動2之前的位置葵硕， 變成了 1（2）眉抬，2（4），4（5）懈凹，5（1）蜀变，括號為挪動前的位置。
時間復(fù)雜度為O(n * n); 性能比選擇排序要好蘸劈。
//直接插入算法
-(void)straightInsertionSort {
NSMutableArray *array = [NSMutableArray arrayWithObjects:@2,@4,@5,@1,@9,@7,@6,@8,@3, nil];
int count = (int)array.count;// NSUInteger 轉(zhuǎn)化為 int 昏苏，要不有問題
NSNumber *temp = nil;
int i, j;
for (i = 1; i < count; i++) {//從第二個元素開始
temp = array[i];
for (j = i; j > 0 && array[j-1]>temp; j--) {
array[j] = array[j-1];
}
array[j] = temp;
}
NSLog(@"%@", array);
}
4.希爾算法
希爾排序為不穩(wěn)定性排序。因為相同的元素可能在各自的插入排序中移動威沫，所以它的穩(wěn)定性就被打破了⊥葑ǎ可能有人想問棒掠，穩(wěn)定性是干嘛的啊屁商？穩(wěn)定的意思是指相同的元素在排序后的相對位置不變烟很。比如有兩個5 ，作為區(qū)分前面的叫5(1)蜡镶，后面的叫5(2)雾袱，排序完成后5(1)還在5(2)的前面。那你可能會問官还，反正是一樣的芹橡，換了就換唄。但是在實際應(yīng)用中被排序的對象會擁有不同的屬性望伦，舉個栗子林说，公司在招聘時煎殷，想要年齡小的，所以對所有人進(jìn)行了按年齡的排序腿箩。之后還想看成績分?jǐn)?shù)高的豪直。所以在按成績進(jìn)行排序時就有可能出現(xiàn)成績一樣的，但他們的年齡不一樣珠移，而你不能把成績相同但年齡大的排在小的前面弓乙。此時算法的穩(wěn)定性就有了意義。
時間復(fù)雜度為O(n^(3/2); 性能比插入排序要好钧惧， 不穩(wěn)定排序唆貌。
#pragma mark - 希爾算法
-(void)shellSort {
NSMutableArray *array = [NSMutableArray arrayWithObjects:@2,@4,@5,@1,@9,@7,@6,@8,@3, nil];
int count = (int)array.count;
//初始增量為數(shù)組長度的一半，然后每次除以2取整
for (int increment = count/2; increment>0; increment /=2) {
//初始下標(biāo)設(shè)為第一個增量的位置垢乙，然后遞增
for (int i = increment; i<count; i++) {
//獲取當(dāng)前位置
int j = i;
//然后將此位置之前的元素锨咙，按照增量進(jìn)行跳躍式比較
while (j-increment>=0 && array[j]<array[j-increment]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
j-=increment;
}
}
}
NSLog(@"%@", array);
}
5.堆排序算法
時間復(fù)雜度為O(nlogn); 不穩(wěn)定排序
/堆排序算法
-(void)HeapSort {
/*
測試數(shù)據(jù)
*/
NSArray *array=@[@3,@2,@6,@4,@1,@0,@6,@7,@5];
NSMutableArray *mutable=[NSMutableArray arrayWithArray:array];
mutable=[self createMaxHeap:mutable];
//NSInteger num=mutable.count;
/*
剩余的元素個數(shù)不為1時則繼續(xù)調(diào)整，取出元素追逮。取出的元素放在最后的一個節(jié)點酪刀。然后減小堆的元素的個數(shù)。所以大頂堆排序出來的是升序的钮孵。
*/
for (NSInteger num=mutable.count; num > 1; num--){
[mutable exchangeObjectAtIndex:0 withObjectAtIndex:num-1];
mutable=[self maxHeapAdjust:mutable index:0 length:num-1];
}
NSLog(@"%@", mutable);
//主要思路：
//1.如何構(gòu)建由一個無序序列建成的一個堆
//2.如何在輸出堆頂元素后骂倘，調(diào)整剩余元素成為一個新的堆
}
-(NSMutableArray*)createMaxHeap:(NSMutableArray*)array
{
/*
從最后一個非葉子節(jié)點開始 自下而上進(jìn)行調(diào)整堆
*/
for (NSInteger i=(array.count/2-1);i>=0; --i)
{
array=[self maxHeapAdjust:array index:i length:array.count] ;
}
return array;
}
/*
調(diào)整堆 遞歸調(diào)整的過程。這個調(diào)整堆的方法傳入的是待調(diào)整的數(shù)組巴席，數(shù)組元素的長度（為什么不直接用array.count呢历涝？因為再進(jìn)行排序
的時候，我們會動態(tài)更改無序堆的長度漾唉，而array的長度確是不變的荧库，所以不用array.cout） 其實每調(diào)用一次調(diào)整堆方法，我們相當(dāng)于只調(diào)整3個元素：父節(jié)點赵刑，左分衫、右子節(jié)點。當(dāng)左子結(jié)點是三者中最大的時候般此，把它和父節(jié)點進(jìn)行交換蚪战。然后再遞歸調(diào)整以剛才的父節(jié)點（現(xiàn)在被降級為左子節(jié)點）為父節(jié)點的三個節(jié)點。此時為什么不用調(diào)整右子節(jié)點呢铐懊？這是由于我們建立大頂堆的過程中邀桑，都是自下而上進(jìn)行調(diào)整的，此時我們沒有動右子節(jié)點科乎，且右子節(jié)點和現(xiàn)在的父節(jié)點（原來的左子節(jié)點）滿足大頂堆的條件壁畸，所以不用調(diào)整。
*/
-(NSMutableArray*)maxHeapAdjust:(NSMutableArray *)array index:(NSInteger)index length:(NSInteger)length
{
NSInteger leftChildIndex =index*2+1;//獲取該節(jié)點的左子節(jié)點索引
NSInteger rightChildIndex=index*2+2;//獲取該節(jié)點的右子節(jié)點索引
NSInteger maxValueIndex=index;//暫時把該索引當(dāng)做最大值所對應(yīng)的索引
// leftChildIndex<length你
//array[leftChildIndex]>array[maxValueIndex] 判斷左子節(jié)點的值是否大于當(dāng)前最大值
if (leftChildIndex<length && array[leftChildIndex]>array[maxValueIndex])
{
//把左子節(jié)點的索引作為最大值所對應(yīng)的索引
maxValueIndex=leftChildIndex;
}
// rightChildIndex<length
//array[leftChildIndex]>array[maxValueIndex] 判斷左子節(jié)點的值是否大于當(dāng)前最大值
if (rightChildIndex<length && array[rightChildIndex]>array[maxValueIndex])
{
maxValueIndex=rightChildIndex;
}
//如果該節(jié)點不是最大值所在的節(jié)點 則將其和最大值節(jié)點進(jìn)行交換
if (maxValueIndex!=index)
{
[array exchangeObjectAtIndex:maxValueIndex withObjectAtIndex:index];
//遞歸鄉(xiāng)下調(diào)整喜喂，此時maxValueIndex索引所對應(yīng)的值是 剛才的父節(jié)點瓤摧。
array=[self maxHeapAdjust:array index:maxValueIndex length:length];
}
return array;
}
6.歸并排序
時間復(fù)雜度為O(nlogn); 穩(wěn)定排序
#pragma mark - 歸并排序
-(void)mergeSort {
NSArray *array=@[@3,@2,@6,@4,@1,@0,@6,@7,@5];
//[self mergeSortWithArray:array];
[self mergeSortWithArray:[NSMutableArray arrayWithArray:array] WithStarIndex:0 WithEndIndex:array.count -1];
//穩(wěn)定排序竿裂， 時間復(fù)雜度為O(nlogn)
}
-(void) mergeSortWithArray: (NSMutableArray *)array
WithStarIndex: (NSInteger) starIndex
WithEndIndex: (NSInteger) endIndex
{
//遞歸結(jié)束條件
if (starIndex >= endIndex) {
return;
}
//找出中點進(jìn)行分解
NSInteger midIndex = (starIndex + endIndex)/2;
//遞歸分解前半部分
[self mergeSortWithArray:array WithStarIndex:starIndex WithEndIndex:midIndex];
//遞歸分解后半部分
[self mergeSortWithArray:array WithStarIndex:midIndex + 1 WithEndIndex:endIndex];
//經(jīng)過上面的遞歸分解后，最小的子數(shù)組里只有一個元素照弥，也就是有序的了腻异，然后從底層進(jìn)行遞歸合并
[self mergeWithArray:array WithStarIndex:starIndex WithMidIndex:midIndex WithEndIndex:endIndex];
}
//一次歸并
-(void) mergeWithArray: (NSMutableArray *)array
WithStarIndex: (NSInteger) starIndex
WithMidIndex: (NSInteger) midIndex
WithEndIndex: (NSInteger) endIndex
{
//記錄歸并次數(shù)
static int sort_count = 0;
if (endIndex < starIndex) {
return;
}
//前半部分元素個數(shù)
NSInteger frontCount = midIndex - starIndex + 1;
//后半部分元素的個數(shù)
NSInteger rearCount = endIndex - midIndex;
//把數(shù)組拆分成兩部分進(jìn)行歸并
//取出前半部分
NSMutableArray *frontArray = [[NSMutableArray alloc] initWithCapacity:frontCount];
for (NSInteger i = 0; i < frontCount; i ++) {
[frontArray addObject:array[starIndex + i]];
}
//取出后半部分
NSMutableArray *rearArray = [[NSMutableArray alloc] initWithCapacity:rearCount];
for (NSInteger i = 0; i < rearCount; i ++) {
[rearArray addObject:array[midIndex + i + 1]];
}
//進(jìn)行比較歸并
NSInteger fi = 0;
NSInteger ri = 0;
NSInteger oi = starIndex;
//當(dāng)兩個子數(shù)組中都有元素時才進(jìn)行合并
while (fi < frontArray.count && ri < rearArray.count) {
if(frontArray[fi] <= rearArray[ri]){
array[oi++] = frontArray[fi++];
continue;
}
array[oi++] = rearArray[ri++];
}
//前面元素中經(jīng)過合并后仍然有元素，把剩余的元素進(jìn)行添加
while (fi < frontArray.count) {
array[oi++] = frontArray[fi++];
}
//后邊元素經(jīng)過合并后仍然有元素这揣，把剩余元素進(jìn)行添加
while (ri < rearArray.count) {
array[oi++] = rearArray[ri++];
}
NSLog(@"第%d合并結(jié)果如下：", ++ sort_count);
NSLog(@"%@", array);//最后一次拿到結(jié)果
}
7.快速排序
時間復(fù)雜度為O(nlogn), 不穩(wěn)定排序,
-(void)quickSort {
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(5),@(9),@(4),@(3),@(7),nil];
NSLog(@"%@",arr);
//不穩(wěn)定排序, 時間復(fù)雜度為O(nlogn)
}
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex) {//如果數(shù)組長度為0或1時返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//記錄比較基準(zhǔn)數(shù)
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先從右邊j開始查找比基準(zhǔn)數(shù)小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基準(zhǔn)數(shù)大悔常，繼續(xù)查找
j--;
}
//如果比基準(zhǔn)數(shù)小，則將查找到的小值調(diào)換到i的位置
array[i] = array[j];
/**** 當(dāng)在右邊查找到一個比基準(zhǔn)數(shù)小的值時给赞，就從i開始往后找比基準(zhǔn)數(shù)大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基準(zhǔn)數(shù)小机打，繼續(xù)查找
i++;
}
//如果比基準(zhǔn)數(shù)大，則將查找到的大值調(diào)換到j(luò)的位置
array[j] = array[i];
}
//將基準(zhǔn)數(shù)放到正確位置
array[i] = @(key);
/**** 遞歸排序 ***/
//排序基準(zhǔn)數(shù)左邊的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基準(zhǔn)數(shù)右邊的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
各種排序的關(guān)系
排序算法關(guān)系圖
最后放上性能的比較圖
各種排序算法的事件復(fù)雜度和穩(wěn)定性
