/*
相关术语解释：
稳定：如果 a 原本在 b 前面，而 a=b，排序之后，a 仍然在 b 的前面
不稳定：不满足稳定定义
内排序（In-place）：所有排序操作都在内存中完成
外排序（Out-place）：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
时间复杂度：一个算法执行所耗费的时间
空间复杂度：运行完一个程序所需内存的大小
n：数据规模
k：「桶」的个数
In-place：不占用额外内存
Out-place：占用额外内存
*/
/*
常用排序算法总结对比
排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 O(n2) O(n) O(n2) O(1) In-place 稳定
选择排序 O(n2) O(n2) O(n2) O(1) In-place 不稳定
插入排序 O(n2) O(n) O(n2) O(1) In-place 稳定
希尔排序 O(n log n) O(n log2 n) O(n log2 n) O(1) In-place 不稳定
归并排序 O(n log n) O(n log n) O(n log n) O(n) Out-place 稳定
快速排序 O(n log n) O(n log n) O(n2) O(log n) In-place 不稳定
堆排序 O(n log n) O(n log n) O(n log n) O(1) In-place 不稳定
计数排序 O(n + k) O(n + k) O(n + k) O(k) Out-place 稳定
桶排序 O(n + k) O(n + k) O(n2) O(n + k) Out-place 稳定
基数排序 O(n x k) O(n x k) O(n x k) O(n + k) Out-place 稳定
*/
///冒泡
///平均时间复杂度 O(n^2),最好情况O(1), 空间复杂度O(1),稳定排序，排序方式:in-place
-(NSArray*)bubbleFunction:(NSMutableArray*)waitingToSort{
for(inti =0; i < waitingToSort.count; i++) {
for(intj =0; j < waitingToSort.count- i -1; j++) {
NSString*temp = waitingToSort[j+1] ;
if([waitingToSort[j]intValue] > [waitingToSort[j+1]intValue]) {
waitingToSort[j+1] = waitingToSort[j];
waitingToSort[j] = temp;
}
}
}
returnwaitingToSort;
}
///选择排序
///选择排序为啥不是稳定性排序呢，举个例子：数组 6、7、6、2、8，在对其进行第一遍循环的时候，会将第一个位置的6与后面的2进行交换。此时，就已经将两个6的相对前后位置改变了。因此选择排序不是稳定性排序算法。
-(NSArray*)chooseAnExampleFuction:(NSMutableArray*)waitingToSort{
for(inti =0; i < waitingToSort.count; i++) {
NSString*temp ;
NSIntegerminIdex =0;
for(intj = i ; j< waitingToSort.count-1; j++) {
minIdex = i;
if([waitingToSort[j+1]intValue] < [waitingToSort[j]intValue]) {
minIdex = j;
}
}
temp = waitingToSort[minIdex];
waitingToSort[minIdex] = waitingToSort[i];
waitingToSort[i] = temp;
}
returnwaitingToSort;
}
/// 插入排序
-(NSArray*)insertionSortFuction:(NSMutableArray*)waitingToSort{
for(inti =1; i
int preIndex = i -1;
NSString*current = waitingToSort[i];
while(preIndex>=0&& [waitingToSort[preIndex]intValue]>[currentintValue]) {
waitingToSort[preIndex+1] = waitingToSort[preIndex];
preIndex--;
}
waitingToSort[preIndex+1] = current;
}
returnwaitingToSort;;
}
//希尔排序
/*1. 算法步骤
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
*/
-(NSArray*)hillSortFuction:(NSMutableArray*)waitingToSort{
intgap =1;
NSString*temp;
NSIntegerlen = waitingToSort.count;
while(gap
gap = gap*3+1;
}
for( ; gap >0; gap = (gap/3)) {
for(inti = gap; i < len; i++) {
temp = waitingToSort[i];
for(intj = i-gap ; j>0&&[waitingToSort[j]intValue] > [tempintValue]
; j -= gap) {
waitingToSort[j+gap] = waitingToSort[j];
waitingToSort[j] = temp ;
}
}
}
returnwaitingToSort;
}
网友评论