排序算法详细过程:选择排序
demo地址:https://github.com/weiman152/PaiXu.git 选择排序是先比较,并不急着交换,而是记录最小的值的位置,把最小的值与第一个位置的值进行交换。然后第二轮的时候,再次遍历除了第一个位置的之外的其他数字,找出最小的,放在第二个位置。以此类推,最后得出排序后的数组。假如数组的个数为n,选择排序会进行 n+(n-1)+(n-2)+......+2+1次比较,最多进行n次交换。下面进行举例说明:(这里为了更加容易理解,把每一次的比较都列了出来) qiaoba5.png 1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48 i: 第几轮比较 min: 当前最小值的下标 j: 同一轮中每一个值与最小值的比较 i=0://第一轮 min = 0 (步骤中用 m 代表) j=1: 1(m), 16(), 23, 56, 89, 33, 7, 27, 55, 37, 48 j=2: 1(m), 16, 23(), 56, 89, 33, 7, 27, 55, 37, 48 j=3: 1(m), 16, 23, 56(), 89, 33, 7, 27, 55, 37, 48 j=4: 1(m), 16, 23, 56, 89(), 33, 7, 27, 55, 37, 48 j=5: 1(m), 16, 23, 56, 89, 33(), 7, 27, 55, 37, 48 j=6: 1(m), 16, 23, 56, 89, 33, 7(), 27, 55, 37, 48 j=7: 1(m), 16, 23, 56, 89, 33, 7, 27(), 55, 37, 48 j=8: 1(m), 16, 23, 56, 89, 33, 7, 27, 55(), 37, 48 j=9: 1(m), 16, 23, 56, 89, 33, 7, 27, 55, 37(), 48 j=10: 1(m), 16, 23, 56, 89, 33, 7, 27, 55, 37, 48() 第一轮比较完成结果:(找到最小值1,放到第一个位置,共比较了 n-1 次) 结果: 1(m), 16, 23, 56, 89, 33, 7, 27, 55, 37, 48 i=1://第二轮 min = 1 j=2: 1(️), 16(m), 23(), 56, 89, 33, 7, 27, 55, 37, 48 j=3: 1(️), 16(m), 23, 56(), 89, 33, 7, 27, 55, 37, 48 j=4: 1(️), 16(m), 23, 56, 89(), 33, 7, 27, 55, 37, 48 j=5: 1(️), 16(m), 23, 56, 89, 33(), 7, 27, 55, 37, 48 j=6: 1(️), 16(m), 23, 56, 89, 33, 7(), 27, 55, 37, 48 j=7: 1(️), 16, 23, 56, 89, 33, 7(m), 27(), 55, 37, 48 j=8: 1(️), 16, 23, 56, 89, 33, 7(m), 27, 55(), 37, 48 j=9: 1(️), 16, 23, 56, 89, 33, 7(m), 27, 55, 37(), 48 j=10: 1(️), 16, 23, 56, 89, 33, 7(m), 27, 55, 37, 48() 比较完成之后交换 : 1(️), 7(m), 23, 56, 89, 33, 16, 27, 55, 37, 48 第二轮比较结果: 1(️), 7(m), 23, 56, 89, 33, 16, 27, 55, 37, 48 i=2://第三轮 min = 2 j=3:1(️), 7(️), 23(m), 56(), 89, 33, 16, 27, 55, 37, 48 j=4:1(️), 7(️), 23(m), 56, 89(), 33, 16, 27, 55, 37, 48 j=5:1(️), 7(️), 23(m), 56, 89, 33(), 16, 27, 55, 37, 48 j=6:1(️), 7(️), 23(m), 56, 89, 33, 16(), 27, 55, 37, 48 j=7:1(️), 7(️), 23, 56, 89, 33, 16(m), 27(), 55, 37, 48 j=8:1(️), 7(️), 23, 56, 89, 33, 16(m), 27, 55(), 37, 48 j=8:1(️), 7(️), 23, 56, 89, 33, 16(m), 27, 55, 37(), 48 j=8:1(️), 7(️), 23, 56, 89, 33, 16(m), 27, 55, 37, 48() 交换:1(️), 7(️), 16(m), 56, 89, 33, 23, 27, 55, 37, 48() 第三轮比较结果: 1(️), 7(️), 16(m), 56, 89, 33, 23, 27, 55, 37, 48 i=3://第四轮 min = 3 j=4:1(️), 7(️), 16(️), 56(m), 89(), 33, 23, 27, 55, 37, 48 j=5:1(️), 7(️), 16(️), 56(m), 89, 33(), 23, 27, 55, 37, 48 j=6:1(️), 7(️), 16(️), 56, 89, 33, 23(), 27, 55, 37, 48 j=7:1(️), 7(️), 16(️), 56, 89, 33, 23(m), 27(), 55, 37, 48 j=8:1(️), 7(️), 16(️), 56, 89, 33, 23(m), 27, 55(), 37, 48 j=9:1(️), 7(️), 16(️), 56, 89, 33, 23(m), 27, 55, 37(), 48 j=10:1(️), 7(️), 16(️), 56, 89, 33, 23(m), 27, 55, 37, 48() 交换:1(️), 7(️), 16(️), 23(m), 89, 33, 56, 27, 55, 37, 48 第四轮比较结果: 1(️), 7(️), 16(️), 23(m), 89, 33, 56, 27, 55, 37, 48 ......... 四轮比较下来,确认了前四个最小值。 下面我们就使用不同语言把代码写出来吧。 OC语言: main函数: #import <Foundation/Foundation.h> #import "Sort.h" int main(int argc, const char * argv[]) { @autoreleasepool { //选择排序 NSMutableArray * arr2= [NSMutableArray arrayWithArray:@[@1,@16,@23,@56,@89,@33,@7,@27,@55,@37,@48]]; NSArray * select = [sort selectedSortWithArray:arr2]; NSLog(@"选择: %@",select); } return 0; } Sort类: Sort.h: #import <Foundation/Foundation.h> @interface Sort : NSObject /** 选择排序 @param array 排序前的数组 @return 排序后的数组 */ - (NSArray *)selectedSortWithArray:(NSMutableArray *)array; Sort.m: #import "Sort.h" @implementation Sort - (NSArray *)selectedSortWithArray:(NSMutableArray *)array { NSMutableArray * arr = [array mutableCopy]; int min = 0; for (int j = 0; j<arr.count-1; j++) { min = j;//最小值下标记录 for (int i = j+1; i<arr.count; i++) { if (arr[min] > arr[i]) { min = i; } } if (min!=j) { [arr exchangeObjectAtIndex:min withObjectAtIndex:j]; } } return arr; } @end Swift语言 main.swift import Foundation let mySort: Sort = Sort() let arr2: [Int] = [1,16,23,56,89,33,7,27,55,37,48] mySort.selectedSort(array: arr2) Sort.swift // // Sort.swift // Sort_Swift // // Created by iOS on 2018/3/13. // Copyright © 2018年 weiman. All rights reserved. // import Cocoa class Sort: NSObject { /// 选择排序 /// /// - Parameter array: 需要排序的数组 func selectedSort(array: [Int]) { var arr = array //记录最小值的下标 var min = 0; for i in 0..<arr.count-1 { min = i for j in i+1..<arr.count { if arr[j] < arr[min] { min = j } } if min != i { arr.swapAt(i, min) } } print("选择排序: \(arr)") } } C语言 // // main.c // Sort_C // // Created by iOS on 2018/3/13. // Copyright © 2018年 weiman. All rights reserved. // #include <stdio.h> void selectedSort(int a[], int size); int main(int argc, const char * argv[]) { printf("Hello, World!\n"); int arr[] = {1,16,23,56,89,33,7,27,55,37,48}; int sizeA = sizeof(arr)/sizeof(arr[0]); selectedSort(arr, sizeA); for(int i=0; i<sizeA; i++){ printf(" %d ",arr[i]); } printf("\n"); return 0; } /** 选择排序 @param a 排序的数组 @param size 数组的长度 */ void selectedSort(int a[], int size){ int min = 0; for (int i = 0; i< size-1; i++) { min = i; for (int j=i+1; j<size; j++) { if (a[j]<a[min]) { min = j; } } if (min != i) { int tmp = a[i]; a[i] = a[min]; a[min] = tmp; } } } 排序前: [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] 打印下排序执行的每一个步骤: i:0,j:1 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:0,j:2 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:0,j:3 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:0,j:4 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:0,j:5 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:0,j:6 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:0,j:7 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:0,j:8 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:0,j:9 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:0,j:10 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:1,j:2 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:1,j:3 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:1,j:4 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:1,j:5 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:1,j:6 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:1,j:7 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:1,j:8 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:1,j:9 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:1,j:10 [1, 16, 23, 56, 89, 33, 7, 27, 55, 37, 48] i:2,j:3 [1, 7, 23, 56, 89, 33, 16, 27, 55, 37, 48] i:2,j:4 [1, 7, 23, 56, 89, 33, 16, 27, 55, 37, 48] i:2,j:5 [1, 7, 23, 56, 89, 33, 16, 27, 55, 37, 48] i:2,j:6 [1, 7, 23, 56, 89, 33, 16, 27, 55, 37, 48] i:2,j:7 [1, 7, 23, 56, 89, 33, 16, 27, 55, 37, 48] i:2,j:8 [1, 7, 23, 56, 89, 33, 16, 27, 55, 37, 48] i:2,j:9 [1, 7, 23, 56, 89, 33, 16, 27, 55, 37, 48] i:2,j:10 [1, 7, 23, 56, 89, 33, 16, 27, 55, 37, 48] i:3,j:4 [1, 7, 16, 56, 89, 33, 23, 27, 55, 37, 48] i:3,j:5 [1, 7, 16, 56, 89, 33, 23, 27, 55, 37, 48] i:3,j:6 [1, 7, 16, 56, 89, 33, 23, 27, 55, 37, 48] i:3,j:7 [1, 7, 16, 56, 89, 33, 23, 27, 55, 37, 48] i:3,j:8 [1, 7, 16, 56, 89, 33, 23, 27, 55, 37, 48] i:3,j:9 [1, 7, 16, 56, 89, 33, 23, 27, 55, 37, 48] i:3,j:10 [1, 7, 16, 56, 89, 33, 23, 27, 55, 37, 48] i:4,j:5 [1, 7, 16, 23, 89, 33, 56, 27, 55, 37, 48] i:4,j:6 [1, 7, 16, 23, 89, 33, 56, 27, 55, 37, 48] i:4,j:7 [1, 7, 16, 23, 89, 33, 56, 27, 55, 37, 48] i:4,j:8 [1, 7, 16, 23, 89, 33, 56, 27, 55, 37, 48] i:4,j:9 [1, 7, 16, 23, 89, 33, 56, 27, 55, 37, 48] i:4,j:10 [1, 7, 16, 23, 89, 33, 56, 27, 55, 37, 48] i:5,j:6 [1, 7, 16, 23, 27, 33, 56, 89, 55, 37, 48] i:5,j:7 [1, 7, 16, 23, 27, 33, 56, 89, 55, 37, 48] i:5,j:8 [1, 7, 16, 23, 27, 33, 56, 89, 55, 37, 48] i:5,j:9 [1, 7, 16, 23, 27, 33, 56, 89, 55, 37, 48] i:5,j:10 [1, 7, 16, 23, 27, 33, 56, 89, 55, 37, 48] i:6,j:7 [1, 7, 16, 23, 27, 33, 56, 89, 55, 37, 48] i:6,j:8 [1, 7, 16, 23, 27, 33, 56, 89, 55, 37, 48] i:6,j:9 [1, 7, 16, 23, 27, 33, 56, 89, 55, 37, 48] i:6,j:10 [1, 7, 16, 23, 27, 33, 56, 89, 55, 37, 48] i:7,j:8 [1, 7, 16, 23, 27, 33, 37, 89, 55, 56, 48] i:7,j:9 [1, 7, 16, 23, 27, 33, 37, 89, 55, 56, 48] i:7,j:10 [1, 7, 16, 23, 27, 33, 37, 89, 55, 56, 48] i:8,j:9 [1, 7, 16, 23, 27, 33, 37, 48, 55, 56, 89] i:8,j:10 [1, 7, 16, 23, 27, 33, 37, 48, 55, 56, 89] i:9,j:10 [1, 7, 16, 23, 27, 33, 37, 48, 55, 56, 89] 选择排序结果: [1, 7, 16, 23, 27, 33, 37, 48, 55, 56, 89]