今天学习了一篇关于排序算法的文章,就想记录一下作为笔记,所以我就写一篇文章,并且附上小片段代码.
1.冒泡排序
大概的过程就是,从第一个元素开始,将它与下一个元素进行比较,如果第一个元素比第二个元素大,那么交换他们的位置.然后再比较第二个和第三个元素,以此类推.在完成第一轮的比较之后,最大的元素会移动到数组的最后,然后进入下一轮的循环,但是此次不再需要对比最后一个元素了,重复这个过程,直到所有的元素都是有序的.
以我个人的理解,它之所以叫做冒泡排序,就是每次比较都会出现一个最大的值放在数组的最后,所以就像冒泡一样,每次比较会出来一个泡,知道所有元素都排序完.哈哈,纯属个人理解.
下面写一段示例看一下:
NSArray *array = @[@"17",@"28",@"36",@"15",@"39"];
NSMutableArray *mutaArr = [array mutableCopy];
NSLog(@"排序前:%@",mutaArr);
for (int j = 0; j < mutaArr.count - 1; j++) {
for (int i = 0; i < mutaArr.count - 1 - j; i++) {
if ([mutaArr[i] intValue] > [mutaArr[i + 1] intValue]) {
int temp = [mutaArr[i] intValue];
mutaArr[i] = mutaArr[i + 1];
//OC中的数组只能存储对象，所以这里转换成string对象
mutaArr[i + 1] = [NSString stringWithFormat:@"%d",temp];
}
}
}
NSLog(@"排序后%@",mutaArr);
有兴趣的同学可以试一下,看看对不对.
2.选择排序
大概过程是选择数组中最小的一个元素,将它与第一个元素交换,然后再从剩下的元素中选择最小的,与第二个元素交换.以此类推,直到遍历完整个数组.
我们看一下示例代码:
NSArray *array1 = @[@"99",@"28",@"53",@"13",@"60",@"78"];
NSMutableArray *mutaArr1 = [array1 mutableCopy];
NSLog(@"mutaArr1排序前%@",mutaArr1);
//声明一个最小值的下标
int minNum;
for (int i = 0; i < mutaArr1.count; i++) {
//找到数组里的最小值的下标
minNum = i;
//遍历数组里除最小值以外的其他元素
for (int j = i + 1; j < mutaArr1.count; j++) {
if ([mutaArr1[j] compare:mutaArr1[minNum]] == NSOrderedAscending) {//比较遍历出来的最小值与刚才取出的最小值
//如果小于刚才取出来的最小值,那么交换两个元素的位置
[mutaArr1 exchangeObjectAtIndex:j withObjectAtIndex:minNum];
}
}
}
NSLog(@"mutaArr1排序后%@",mutaArr1);
经过测试,排序成功.
3.插入排序
基本思想就是将一个新数据插入到一个有序的数组中.最开始的时候,这个有序的数组是空的,我们就把待排序的数组的第一个元素放到有序的数组中,那么此时,有序的数组就有了第一个元素.
1.然后再取待排序数组中的第二个元素放到有序的数组中,此时就需要比较一下插入的元素与有序数组中的元素的大小,如果比有序数组中的元素小,那么就放在第一个位置,原来有序数组中的元素右移一位.反之,就放在有序数组中原有元素的后面.
(一般的帖子,写到这就是以此类推了,但是为了理解的更好,我再往下说一步,这样就能更好的理解插入排序了).
2.接着,取出待排序数组中的第三个元素放到有序数组中,依然需要比较,只是比较的次数多一次,因为此时有序数组中有两个元素了,怎么比较呢?
先拿待排序数组中的第三个元素与有序数组中的第二个元素相比较,如果比第二个元素小,那么有序数组中第二个元素后移一位,插入的元素占有它原来的位置.
然后再拿刚才插入的元素与有序数组中第一个元素相比,如果比它小,那么第一个元素也要后移一位,它再占据第一个元素原来的位置,如此一来,前几个元素已经排序好了,下面就是以此类推了.
虽然看着很赘述,但是我觉得说的比较清楚一点有助于理解,语文水平不要,不要介意......
下面看一下示例代码:
NSArray *array2 = @[@"3",@"5",@"1",@"4",@"2",@"8",@"6",@"9",@"7"];
NSMutableArray *mutaArr2 = [array2 mutableCopy];
NSLog(@"mutaArr2排序前:%@",mutaArr2);
//从待排序数组取出第二个元素(下标为1)
for (int i = 1; i < mutaArr2.count; i++) {
//j代表需要取出的元素的下标,先确定下标,在取出待排序的数字
int j = i;
//取出待排序下标的元素
int temp = [mutaArr2[i] intValue];
//如果取出的元素小于有序数组中它前面的元素
while (j > 0 && temp < [mutaArr2[j - 1] intValue]) {
//把比较大的数放在后面(即比较大的元素右移以为)
mutaArr2[j] = mutaArr2[j - 1];
j--;//再次排序
}
mutaArr2[j] = [NSString stringWithFormat:@"%d",temp];
}
NSLog(@"mutaArr2排序后:%@",mutaArr2);
这样排序就成功了.其实照着示例代码,还是比较好理解的.
4.希尔排序
希尔排序是通过设置步长来让元素可以一次移动较长的距离来减少元素移动的次数来大到比插入排序更好的效果的.
说一下我的思路:首先需要先设置一个步长,然后取出以步长作为下标的那个元素(步长为整形数据),然后让它与第一个元素进行比较,
如果比第一个元素小,那么交换这两个元素的位置,反之,元素位置不变.
接着再取出以步长+1为下标的那个元素,与第二个元素相比较,
如果比第二个元素小,那么交换这两个元素的位置,反之,元素位置也不变.
以此类推......
下面看一下示例代码:
NSArray *array3 = @[@"19",@"12",@"16",@"18",@"17",@"10",@"13",@"15",@"14",@"11"];
NSMutableArray *mutaArr3 = [array3 mutableCopy];
NSLog(@"mutaArr3排序前:%@",mutaArr3);
//先确定一个步长,作为遍历的起始
int step = (int)mutaArr3.count / 2;
while (step >= 1) {
//从以步长为下标的元素开始,遍历数组
for (int i = step; i < mutaArr3.count; i++) {
int temp = [[mutaArr3 objectAtIndex:i] intValue];//取出一个元素
int j = i;
//此处用数字来说明更明朗:此时的step = 5,那么i也是5,j也是5,temp的值是下标为5的那个元素,也就是10,[mutaArr3 objectAtIndex:j - step]的值是第一个元素,也就是19.那么判断也就是while(5 >= 5 && 10 < 19) 此时的判断成立
while (j >= step && temp < [[mutaArr3 objectAtIndex:j - step] intValue]) {
//将数值较大的那个元素放到下标为5的位置
j -= step;//此时j = 0,再走while判断时,判断也就是while(0 >= 5 && 10....) 明显判断不成立,跳出判断走下一句代码
[mutaArr3 replaceObjectAtIndex:j withObject:[mutaArr3 objectAtIndex:j - step]];
}
//这行代码是在while判断不成立时走的,不成立时,直接把当前temp的值放到下标为j的元素的位置,注意每次走while判断时,j值的变化
[mutaArr3 replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%d",temp]];
}
//当元素全部遍历时,缩小步长,重新判断,进行排序
step = step / 2;
}
NSLog(@"mutaArr3排序后:%@",mutaArr3);
此时排序成功.如果觉得有点难懂的话,将代码拷贝进工程里,配合注释,打断点看值的变化,就比较容易理解了.
5.快速排序
大致的思路就是:选择一个数作为基准,将所有小于基准的数都放到左边,大于基准的数都放到右边,然后再对左右两边的数组进行快速排序,可以选择使用递归的方法,直到整个数组变为有序的.
示例代码:
NSArray *array4 = @[@"25",@"24",@"27",@"21",@"23",@"29",@"28",@"22",@"26"];
NSMutableArray *mutaArr4 = [array4 mutableCopy];
NSLog(@"mutaArr4排序前:%@",mutaArr4);
[self quickSortArray:mutaArr4 withLeftIndex:0 andRightIndex:mutaArr4.count - 1];
NSLog(@"mutaArr4排序后:%@",mutaArr4);
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex) {//如果数组长度为0或1时直接返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//记录比较基准数
NSInteger baseValue = [array[i] integerValue];
while (i < j) {
//首先从右边j开始查找比基准数小的值
while (i < j && [array[j] integerValue] >= baseValue) {//如果比基准数大，继续往前查找
j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置
array[i] = array[j];
//当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值
while (i < j && [array[i] integerValue] <= baseValue) {//如果比基准数小，继续往后查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
array[j] = array[i];
}
//将基准数放到正确位置
array[i] = [NSString stringWithFormat:@"%ld",baseValue];
/**** 递归排序 ***/
//排序基准数左边的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
其实基本的思想就是:选择一个基准后,
1.先从后往前排序,如果这个数比基准大,则不做操作,继续往前选,如果比基准数小,则将查找到的值调换到i的位置
2.当在右边查找到一个比基准数小的值时,就从i开始往后找比基准数大的值,如果比基准数小,不做操作,如果比基准数大,则将查找到的值调换到j的位置
3.对照示例代码看,更容易理解.
6.归并排序
归并排序就是将一个无序数组拆分成多个只有一个元素的有序数组,然后进行两两合并.在合并的过程中,对相比较的两个数组进行排序,这样合并后数组依然是有序的.然后再进行两两合并,直到合并为一个数组为止.归并排序时分治法的典型应用.
看一下具体代码:
NSArray *array5 = @[@"36",@"34",@"37",@"32",@"33",@"39",@"38",@"31",@"35"];
NSMutableArray *mutaArr5 = [array5 mutableCopy];
NSLog(@"mutaArr5排序前:%@",mutaArr5);
[self mergeSortArray:mutaArr5 lowIndex:0 highIndex:mutaArr5.count - 1];
NSLog(@"mutaArr5排序后:%@",mutaArr5);
//归并排序
- (void)mergeSortArray:(NSMutableArray *)array lowIndex:(NSInteger)lowIndex highIndex:(NSInteger)highIndex
{
if (lowIndex >= highIndex) {
return;
}
NSInteger midIndex = lowIndex + (highIndex - lowIndex) / 2;
[self mergeSortArray:array lowIndex:lowIndex highIndex:midIndex];
[self mergeSortArray:array lowIndex:midIndex + 1 highIndex:highIndex];
[self mergeArray:array lowIndex:lowIndex midIndex:midIndex highIndex:highIndex];
}
- (void)mergeArray:(NSMutableArray *)array lowIndex:(NSInteger)lowIndex midIndex:(NSInteger)midIndex highIndex:(NSInteger)highIndex
{
for (NSInteger i = lowIndex; i <= highIndex; i ++) {
self.tempArr[i] = array[i];
}
NSInteger k = lowIndex;
NSInteger l = midIndex + 1;
for (NSInteger j = lowIndex; j <= highIndex; j ++) {
if (l > highIndex) {
array[j] = self.tempArr[k];
k++;
}else if (k > midIndex)
{
array[j] = self.tempArr[l];
l++;
}else if ([self.tempArr[k] integerValue] > [self.tempArr[l] integerValue])
{
array[j] = self.tempArr[l];
l++;
}else
{
array[j] = self.tempArr[k];
k++;
}
}
}
先学习这么多吧,其他的几种排序方法我还没看懂,等看懂了再记录下来.感谢开源带来的便捷.
