排序算法

排序算法

  • 冒泡排序
  • 选择排序
  • 直接插入排序
  • 希尔排序
  • 快速排序

冒泡排序

冒泡排序是一种交换排序,基本思想是两两相邻的记录的关键字,如果反序则交换,知道没有反序为止。

冒泡排序的复杂度是n(n-1)/2,就是o(n²)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*对顺序列表排序*/
-(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²),性能略优于冒泡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
-(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²)。
性能略优于选择排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-(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时,整个文件恰被分成一组,算法便终止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//希尔排序算法
-(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²)。

快速排序

基本思想是:通过一趟排序将带排序记录分割成独立的两部分,其中一部分记录的关键字均比另外一部分的关键字小,则可分别对着两部分重新排序,以达到整个序列的有序的目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 快速排序
-(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)。

优化选择枢轴
三数取中发,就是取三个关键字排序,将中间的数作为枢轴,一般是取左,右,中间三个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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];

优化不必要的交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//返回在他前后记录均不大(小)与他。
-(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;
}