Objective-C實現常用的4種排序演算法

NO IMAGE

OC實現的4種排序又來了!

4種排序分別是:快速排序、氣泡排序、選擇排序、插入排序,其他的我就不寫了,因為OC裡的陣列中不能存放基本資料型別,如int不能存放,只能放物件,所以所有的資料我用了NSNumber型別,一開始我直接用>、=、<來比較結果排序後還是亂七八糟,後來想起來不能這麼比較,物件的比較,可以用compare方法,結果與NSComparisonResult這個列舉型別的資料比較大小就可以了。或者取NSNumber 的intValue,在用>、=、<進行比較,第一個方法中有些兩種方式的語句,後來的類似就不寫了。

1、快速排序

#pragma - mark 快速排序
(void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high
{
if(array == nil || array.count == 0){
return;
}
if (low >= high) {
return;
}
//取中值
int middle = low   (high - low)/2;
NSNumber *prmt = array[middle];
int i = low;
int j = high;
//開始排序,使得left<prmt 同時right>prmt
while (i <= j) {
//        while ([array[i] compare:prmt] == NSOrderedAscending) {  該行與下一行作用相同
while ([array[i] intValue] < [prmt intValue]) {
i  ;
}
//        while ([array[j] compare:prmt] == NSOrderedDescending) { 該行與下一行作用相同
while ([array[j] intValue] > [prmt intValue]) {
j--;
}
if(i <= j){
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
i  ;
j--;
}
printf("排序中:");
[self printArray:array];
}
if (low < j) {
[self quickSort:array low:low high:j];
}
if (high > i) {
[self quickSort:array low:i high:high];
}
}

快速排序的過程如下:

排序前:9 2 10 7 3 7 4 
排序中:4 2 10 7 3 7 9 
排序中:4 2 7 7 3 10 9 
排序中:4 2 7 3 7 10 9 
排序中:2 4 7 3 7 10 9 
排序中:2 4 3 7 7 10 9 
排序中:2 3 4 7 7 10 9 
排序中:2 3 4 7 7 9 10 
排序中:2 3 4 7 7 9 10 
排序後:2 3 4 7 7 9 10

2、氣泡排序

#pragma - mark 氣泡排序
(void)buddleSort:(NSMutableArray *)array
{
if(array == nil || array.count == 0){
return;
}
for (int i = 1; i < array.count; i  ) {
for (int j = 0; j < array.count - i; j  ) {
if ([array[j] compare:array[j 1]] == NSOrderedDescending) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j 1];
}
printf("排序中:");
[self printArray:array];
}
}
}

氣泡排序的過程如下:

排序前:9 2 10 7 3 7 4 
排序中:2 9 10 7 3 7 4 
排序中:2 9 10 7 3 7 4 
排序中:2 9 7 10 3 7 4 
排序中:2 9 7 3 10 7 4 
排序中:2 9 7 3 7 10 4 
排序中:2 9 7 3 7 4 10 
排序中:2 9 7 3 7 4 10 
排序中:2 7 9 3 7 4 10 
排序中:2 7 3 9 7 4 10 
排序中:2 7 3 7 9 4 10 
排序中:2 7 3 7 4 9 10 
排序中:2 7 3 7 4 9 10 
排序中:2 3 7 7 4 9 10 
排序中:2 3 7 7 4 9 10 
排序中:2 3 7 4 7 9 10 
排序中:2 3 7 4 7 9 10 
排序中:2 3 7 4 7 9 10 
排序中:2 3 4 7 7 9 10 
排序中:2 3 4 7 7 9 10 
排序中:2 3 4 7 7 9 10 
排序中:2 3 4 7 7 9 10 
排序後:2 3 4 7 7 9 10

3、選擇排序

  (void)selectSort:(NSMutableArray *)array
{
if(array == nil || array.count == 0){
return;
}
int min_index;
for (int i = 0; i < array.count; i  ) {
min_index = i;
for (int j = i   1; j<array.count; j  ) {
if ([array[j] compare:array[min_index]] == NSOrderedAscending) {
[array exchangeObjectAtIndex:j withObjectAtIndex:min_index];
}
printf("排序中:");
[self printArray:array];
}
}
}

選擇排序的過程如下:

排序前:9 2 10 7 3 7 4 
排序中:2 9 10 7 3 7 4 
排序中:2 9 10 7 3 7 4 
排序中:2 9 10 7 3 7 4 
排序中:2 9 10 7 3 7 4 
排序中:2 9 10 7 3 7 4 
排序中:2 9 10 7 3 7 4 
排序中:2 9 10 7 3 7 4 
排序中:2 7 10 9 3 7 4 
排序中:2 3 10 9 7 7 4 
排序中:2 3 10 9 7 7 4 
排序中:2 3 10 9 7 7 4 
排序中:2 3 9 10 7 7 4 
排序中:2 3 7 10 9 7 4 
排序中:2 3 7 10 9 7 4 
排序中:2 3 4 10 9 7 7 
排序中:2 3 4 9 10 7 7 
排序中:2 3 4 7 10 9 7 
排序中:2 3 4 7 10 9 7 
排序中:2 3 4 7 9 10 7 
排序中:2 3 4 7 7 10 9 
排序中:2 3 4 7 7 9 10 
排序後:2 3 4 7 7 9 10

4、插入排序

#pragma - mark 插入排序
(void)inserSort:(NSMutableArray *)array
{
if(array == nil || array.count == 0){
return;
}
for (int i = 0; i < array.count; i  ) {
NSNumber *temp = array[i];
int j = i-1;
while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
[array replaceObjectAtIndex:j 1 withObject:array[j]];
j--;
printf("排序中:");
[self printArray:array];
}
[array replaceObjectAtIndex:j 1 withObject:temp];
}
}

插入排序的過程如下:

排序前:9 2 10 7 3 7 4 
排序中:9 9 10 7 3 7 4 
排序中:2 9 10 10 3 7 4 
排序中:2 9 9 10 3 7 4 
排序中:2 7 9 10 10 7 4 
排序中:2 7 9 9 10 7 4 
排序中:2 7 7 9 10 7 4 
排序中:2 3 7 9 10 10 4 
排序中:2 3 7 9 9 10 4 
排序中:2 3 7 7 9 10 10 
排序中:2 3 7 7 9 9 10 
排序中:2 3 7 7 7 9 10 
排序中:2 3 7 7 7 9 10 
排序後:2 3 4 7 7 9 10 

另外,類的程式碼也附上吧!

//
//  SortUtil.h
//  SortUtil
//
//  Created by Mac on 14-4-17.
//  Copyright (c) 2014年 KnightKing. All rights reserved.
//
#import <Foundation/Foundation.h>
@interface SortUtil : NSObject
//快速排序
(void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high;
//氣泡排序
(void)buddleSort:(NSMutableArray *)array;
//選擇排序
(void)selectSort:(NSMutableArray *)array;
//插入排序
(void)inserSort:(NSMutableArray *)array;
//列印陣列
(void)printArray:(NSArray *)array;
@end

//
//  SortUtil.m
//  SortUtil
//
//  Created by Mac on 14-4-17.
//  Copyright (c) 2014年 KnightKing. All rights reserved.
//
#import "SortUtil.h"
@implementation SortUtil
#pragma - mark 快速排序
(void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high
{
if(array == nil || array.count == 0){
return;
}
if (low >= high) {
return;
}
//取中值
int middle = low   (high - low)/2;
NSNumber *prmt = array[middle];
int i = low;
int j = high;
//開始排序,使得left<prmt 同時right>prmt
while (i <= j) {
//        while ([array[i] compare:prmt] == NSOrderedAscending) {  該行與下一行作用相同
while ([array[i] intValue] < [prmt intValue]) {
i  ;
}
//        while ([array[j] compare:prmt] == NSOrderedDescending) { 該行與下一行作用相同
while ([array[j] intValue] > [prmt intValue]) {
j--;
}
if(i <= j){
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
i  ;
j--;
}
printf("排序中:");
[self printArray:array];
}
if (low < j) {
[self quickSort:array low:low high:j];
}
if (high > i) {
[self quickSort:array low:i high:high];
}
}
#pragma - mark 氣泡排序
(void)buddleSort:(NSMutableArray *)array
{
if(array == nil || array.count == 0){
return;
}
for (int i = 1; i < array.count; i  ) {
for (int j = 0; j < array.count - i; j  ) {
if ([array[j] compare:array[j 1]] == NSOrderedDescending) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j 1];
}
printf("排序中:");
[self printArray:array];
}
}
}
#pragma - mark 選擇排序
(void)selectSort:(NSMutableArray *)array
{
if(array == nil || array.count == 0){
return;
}
int min_index;
for (int i = 0; i < array.count; i  ) {
min_index = i;
for (int j = i   1; j<array.count; j  ) {
if ([array[j] compare:array[min_index]] == NSOrderedAscending) {
[array exchangeObjectAtIndex:j withObjectAtIndex:min_index];
}
printf("排序中:");
[self printArray:array];
}
}
}
#pragma - mark 插入排序
(void)inserSort:(NSMutableArray *)array
{
if(array == nil || array.count == 0){
return;
}
for (int i = 0; i < array.count; i  ) {
NSNumber *temp = array[i];
int j = i-1;
while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
[array replaceObjectAtIndex:j 1 withObject:array[j]];
j--;
printf("排序中:");
[self printArray:array];
}
[array replaceObjectAtIndex:j 1 withObject:temp];
}
}
(void)printArray:(NSArray *)array
{
for(NSNumber *number in array) {
printf("%d ",[number intValue]);
}
printf("\n");
}
@end

呼叫我就寫在了app啟動的方法裡:

- (BOOL)application:(UIApplication *)application didFinishLaunchingWithOptions:(NSDictionary *)launchOptions
{
self.window = [[UIWindow alloc] initWithFrame:[[UIScreen mainScreen] bounds]];
// Override point for customization after application launch.
self.window.backgroundColor = [UIColor whiteColor];
[self.window makeKeyAndVisible];
NSMutableArray *array = [NSMutableArray arrayWithObjects:@9,@2,@10,@7,@3,@7,@4,nil];
printf("排序前:");
[SortUtil printArray:array];
//快速排序
//    [SortUtil quickSort:array low:0 high:6];
//氣泡排序
//    [SortUtil buddleSort:array];
//選擇排序
//    [SortUtil selectSort:array];
//插入排序
[SortUtil inserSort:array];
printf("排序後:");
[SortUtil printArray:array];
return YES;
}