选择排序 select sort

选择排序

• 时间复杂度：（平均、最好、最坏）都是O(n^2)
• 控件复杂度：O(1)
• 稳定性：不稳定

算法分析：

1. 从第一个元素开始，用第一个元素和剩余元素比较，找出最大或最小
2. 找到最大或最小后，和当前元素交换
3. 以此类推，直到排序完成

动画演示：

selectionSort

C语言 实现

int *selectSort1(int arr[],int count) {
    int minIndex,tmp;
    for (int i = 0; i<count-1; i++) {
        minIndex = i;
        for (int j = i+1; j<count; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
    return arr;
}

OC 实现

- (NSArray *)selectSort:(NSMutableArray *)arr {//[@1,@20,@5]
    NSNumber *tmp = nil;
    int minIndex = 0;//最小值的index
    for (int i = 0; i<arr.count-1; i++) {
        minIndex = i;
        for (int j = i+1; j<arr.count; j++) {
            if ([arr[minIndex] intValue] > [arr[j] intValue]) {
                minIndex = j;
            }
        }
        tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
    return arr.copy;
}

Swift 实现

func selectSort(arr:Array<Int>) -> Array<Int> {
    var tmp = 0
    var minIndex = 0
    var tmpArr = arr
    for i in 0..<tmpArr.count {
        minIndex = i
        for j in i+1..<tmpArr.count {
            if tmpArr[j] < tmpArr[minIndex] {
                minIndex = j
            }
        }
        tmp = tmpArr[i]
        tmpArr[i] = tmpArr[minIndex]
        tmpArr[minIndex] = tmp
    }
    return tmpArr
}

以下实现来源于网络，未验证

js实现

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

Python 代码实现

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

Go 代码实现

func selectionSort(arr []int) []int {
    length := len(arr)
    for i := 0; i < length-1; i++ {
        min := i
        for j := i + 1; j < length; j++ {
            if arr[min] > arr[j] {
                min = j
            }
        }
        arr[i], arr[min] = arr[min], arr[i]
    }
    return arr
}

Java 代码实现

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
        return arr;
    }
}