排序算法
- 冒泡排序
- 选择排序
- 直接插入排序
- 希尔排序
- 堆排序
- 归并排序
- 快速排序
-计数排序
冒泡排序
冒泡排序是一种交换排序，基本思想是两两相邻的记录的关键字，如果反序则交换，知道没有反序为止。
冒泡排序的复杂度是n(n-1)/2,就是o(n²)。
/*对顺序列表排序*/
-(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次关键字间的比较，从n-i+1个记录选出关键字最小的记录，并和第i（1=《i《=n）交换之。
选择排序复杂度是n（n-1）/2,就是o（n²），性能略优于冒泡。
-(void)sort:(NSMutableArray *)list{
NSInteger i , j , min;
for (i = 1; i < list.count; i ++) {
min = i; //默认最小值是第一个
for (j = i + 1; j <= list.count; j ++) {
if (list[min] > list[j] ) {
min = j; //记录最小值的索引
}
}
if (min != i) {// 出现最小的值的时候 和上个最小的值交换位置
/*
交换obj
*/
[list exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
直接插入排序算法
直接插入排序的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的，记录增加1的有序表。
直接插入排序时间复杂度是（n+4）（n-1）/2，就是o（n²）。
性能略优于选择排序。
-(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];//设置哨兵
for (j = i - 1; j >= 0 && [list[j] integerValue] < data ; j --) {
list[j+1] = list[j];//向后移动一位
}
if (data) {
list[j+1] =@(data);//哨兵赋值
}
}
}
}
希尔排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
//希尔排序算法
-(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，循环次数多。
时间复杂度是o(n的二分之三次方)，优于o（n²）。
堆排序
基本思想是将带排序的序列构造成一个大堆，此时，整个序列的最大值就是堆顶的根节点。将他移走（其实是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序重新构造一个堆，这样会得到n个元素中的次小值。如此反复，便能得到一个有序序列了。
程序暂没有,后期完善。
归并排序
原理是利用初始序列含有n个记录，则可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到【n/2】（【x】表示不小于x的最小整数）个长度为2 或1的有序子列，然后两两归并，。。。。如此重复，直至得到一个长度为n的有序序列，这种排发称为2路归并排序。
程序暂没有,后期完善。
快速排序
基本思想是:通过一趟排序将带排序记录分割成独立的两部分，其中一部分记录的关键字均比另外一部分的关键字小，则可分别对着两部分重新排序，以达到整个序列的有序的目的。
// 快速排序
-(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];//将整个序列一分为二
[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;
}
时间复杂度是o（n²）空间复杂度是o（log n）。
优化选择枢轴
三数取中发，就是取三个关键字排序，将中间的数作为枢轴，一般是取左，右，中间三个数。
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];
优化不必要的交换
//返回在他前后记录均不大（小）与他。
-(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];//取出来适当的关键字
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; //最后 将关键字 赋值给low的位置
return low;
}
归并排序和堆排序暂时没有完善，下一期将完善。
计数排序
缺点是整数型的好牌，小数点的要转化成整数再排序。时间负责度0(n+k)，空间复杂度是o(n+k),性能优于所有比较排序算法。
func countsSort(list:inout [Int],n:Int) -> Void{
let startTime1 = CFAbsoluteTimeGetCurrent();
var dic = [Int:Int]();
//key value 存储数组都读取到dic 中
for index in 0..<n {
let item = list[index];
var value:Int = dic[item] ?? 0;
value += 1;
dic[item] = value;
}
//删除所有的旧数组
list.removeAll();
//根据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");
}
