1.冒泡排序
NSMutableArray *arr_M = [NSMutableArray arrayWithObjects:@"32",@"23",@"11",@"22",@"3",@"232",@"23123",@"43",nil];
for (int i = 0; i < arr_M.count ; i++) {
//遍历数组的每一个`索引`（不包括最后一个,因为比较的是j+1）
for (int j = 0; j < arr_M.count -1 - i; j++) {
//根据索引的`相邻两位`进行`比较`
if ([arr_M[j] integerValue] < [arr_M[j+1] integerValue]) {
[arr_M exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"最终结果：%@",arr_M);
2.选择排序
NSMutableArray *arr_M = [NSMutableArray arrayWithObjects:@"32",@"23",@"11",@"22",@"3",@"232",@"23123",@"43",nil];
for (int i=0; i<arr_M.count ; i++) {
for (int j=i+1; j<arr_M.count; j++) {
if ([arr_M[i] integerValue]<[arr_M[j] integerValue]) {
[arr_M exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
NSLog(@"%@",arr_M);
3.桶排序
NSArray *list = [NSArray arrayWithObjects:@"8",@"3",@"5",@"2",@"5", nil];
NSInteger max = 8; //此地取最大值
NSMutableArray *save = [NSMutableArray arrayWithCapacity:(max+1)]; //此地只需要大于最大值继续
for (NSInteger i = 0; i < (max+1); i++) {
save[i] = @(0);
}
for (NSInteger i = 0; i < list.count; i++) {
NSInteger rl = ((NSString*)list[i]).integerValue;
NSInteger result = ((NSNumber *)save[rl]).integerValue;
result += 1;
save[rl] = @(result);
}
NSLog(@"排序：");
for (NSInteger i = max; i >= 0; i--) {
NSInteger count = ((NSNumber *)save[i]).integerValue;
while (count > 0) {
NSLog(@"%ld", (long)i);
count —;
}
}
4.插入排序
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100, nil];
for (int i = 0; i < dataArr.count; i++) {
for (int j = i; j > 0; j--) {
if ([dataArr[j] intValue] < [dataArr[j - 1] intValue]) {
[dataArr exchangeObjectAtIndex:j withObjectAtIndex:j-1];
}
}
}
NSLog(@"直接插入排序结果----%@",dataArr);
5.希尔排序
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
int n = (int)dataArr.count;
for (int gap = n / 2; gap > 0; gap /= 2){
for (int i = gap; i < n; i++){
for (int j = i - gap; j >= 0 && [dataArr[j] intValue] > [dataArr[j + gap] intValue]; j -= gap){
[dataArr exchangeObjectAtIndex:j withObjectAtIndex:(j + gap)];
}
}
}
NSLog(@"----%@", dataArr);
6.堆排序
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
/* 从最后一个非叶子节点开始 自下而上进行调整堆 */
for (NSInteger i=(dataArr.count/2-1); i >= 0; --i) {
dataArr = [self maxHeapAdjust:dataArr index:i length:dataArr.count] ;
}
NSInteger num = dataArr.count;
/* 剩余的元素个数不为1时则继续调整，取出元素。取出的元素放在最后的一个节点。然后减小堆的元素的个数。所以大顶堆排序出来的是升序的。 */
while (num > 1) {
[dataArr exchangeObjectAtIndex:0 withObjectAtIndex:num-1];
dataArr=[self maxHeapAdjust:dataArr index:0 length:num-1];
num--;
}
NSLog(@"堆排序-----%@",dataArr);
- (NSMutableArray*)maxHeapAdjust:(NSMutableArray *)array index:(NSInteger)index length:(NSInteger)length {
NSInteger leftChildIndex =index*2+1;//获取该节点的左子节点索引
NSInteger rightChildIndex=index*2+2;//获取该节点的右子节点索引
NSInteger maxValueIndex=index;//暂时把该索引当做最大值所对应的索引
// leftChildIndex < length
// 判断左子节点的值是否大于当前最大值
if (leftChildIndex < length && [array[leftChildIndex] integerValue] > [array[maxValueIndex] integerValue]) {
//把左子节点的索引作为最大值所对应的索引
maxValueIndex=leftChildIndex;
}
// rightChildIndex < length
// 判断左子节点的值是否大于当前最大值
if (rightChildIndex < length && [array[rightChildIndex] integerValue] > [array[maxValueIndex] integerValue]) {
maxValueIndex=rightChildIndex;
}
//如果该节点不是最大值所在的节点 则将其和最大值节点进行交换
if (maxValueIndex != index) {
[array exchangeObjectAtIndex:maxValueIndex withObjectAtIndex:index];
//递归乡下调整，此时maxValueIndex索引所对应的值是 刚才的父节点。
array=[self maxHeapAdjust:array index:maxValueIndex length:length];
}
return array;
}
7.快速排序
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
[self quickSortArray:dataArr withLeftIndex:0 andRightIndex:dataArr.count-1];
NSLog(@"快速排序%@",dataArr);
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//记录比较基准数
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先从右边j开始查找比基准数小的值 ***/
while (i < j && [array[j] integerValue] >= key) {
//如果比基准数大，继续查找
j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置
array[i] = array[j];
/**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
while (i < j && [array[i] integerValue] <= key) {
//如果比基准数小，继续查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
array[j] = array[i];
}
//将基准数放到正确位置
array[i] = @(key);
/**** 递归排序 ***/
//排序基准数左边的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
8.归并排序
self.dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
NSMutableArray *tempArray = [NSMutableArray array];
//将数组中的每一个元素放入一个数组中
for (NSNumber *number in self.dataArr) {
NSMutableArray *childArray = [NSMutableArray array];
[childArray addObject:number];
[tempArray addObject:childArray];
}
//对这个数组中的数组进行合并，直到合并完毕为止
while (tempArray.count != 1) {
NSUInteger i = 0;
while (i < tempArray.count - 1) {
tempArray[i] = [self mergeArray:tempArray[i] secondArray:tempArray[i+1]];
[tempArray removeObjectAtIndex:i+1];
i += 1;
}
}
DLog(@"%@",tempArray);
// 归并排序中的“并”--合并：将两个有序数组进行合并
// - parameter firstList: 第一个有序数组
// - parameter secondList: 第二个有序数组
- (NSMutableArray *)mergeArray:(NSMutableArray *)firstArray secondArray:(NSMutableArray *)secondArray {
NSMutableArray *resultArray = [NSMutableArray array];
NSUInteger firstIndex = 0;
NSUInteger secondIndex = 0;
while (firstIndex < firstArray.count && secondIndex < secondArray.count) {
if ([firstArray[firstIndex] integerValue] < [secondArray[secondIndex] integerValue]) {
[resultArray addObject:firstArray[firstIndex]];
firstIndex += 1;
}else {
[resultArray addObject:secondArray[secondIndex]];
secondIndex += 1;
}
}
while (firstIndex < firstArray.count) {
[resultArray addObject:firstArray[firstIndex]];
firstIndex += 1;
}
while (secondIndex < secondArray.count) {
[resultArray addObject:secondArray[secondIndex]];
secondIndex += 1;
}
return resultArray;
}
9.二分法
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
for (int i = 1; i < dataArr.count; i++) {
int left = 0;
int right = i - 1;
int mid;
int temp = [dataArr[i] intValue];
if (temp < [dataArr[right] intValue]) {
while (left <= right) {
mid = (left + right) / 2;
if ([dataArr[mid] intValue] < temp) {
left = mid + 1;
}else if ([dataArr[mid] intValue] > temp) {
right = mid - 1;
}else {
left += 1;
}
}
for (int j = i; j > left; j--) {
[dataArr exchangeObjectAtIndex:j-1 withObjectAtIndex:j];
}
dataArr[left] = [NSNumber numberWithInt:temp];
}
}
NSLog(@"折半插入排序----%@", dataArr);
