关于排序:选择排序

抉择排序

目录

• 1.算法思维
• 2.从[算法思维]到[代码实现]
• 3.代码实现(C、Python)

1. 算法思维

抉择排序：每一轮抉择出 以后未排序区间中最小的元素放到 对应的地位上

排序过程：

数组a有n个元素

• 第一轮：a[0]-a[n-1]为待排序区间，在此区间中选出最小的元素放在a[0]上；
• 第二轮：a[1]-a[n-1]是新的待排序区间，在此区间中选出最小的元素放到a[1]上；

• 第三轮：a[2]-a[n-1]是新的待排序区间，在此区间中选出最小的元素放到a[2]上；

  ….

• 第 n-1 轮：通过下面的排序，从a[0]-a[n-2]顺次放入了最小、次小..的元素，a[0]-a[n-2]为有序区间，此时待排序区间只剩下一个元素即最初一个元素，无需再进行排序，整个数组排序结束。

2.从“算法思维”到“代码实现”

察看上述算法中的排序过程

1. 共须要n-1轮排序，每一轮排序外部的操作都一样，因而能够用for循环来实现每一轮排序。循环变量 i 的取值范畴为[0,n-1]
2. 在每一轮排序外部为了最终找出剩下区间中最小的元素，须要遍历整个剩下的区间。因而每一轮排序外部也有一个for循环。循环变量 j 的取值范畴为[i+1,n-1]

综上所述，算法能够应用2层for循环来实现

• 外层的循环次数是排序轮次，有n个元素，则循环n-1次；这个for循环实现每一轮排序

• 内层for循环实现在每一轮排序外部找出剩下区间中的最小元素

  双层for循环示意图：

3. 代码实现(C、Python)

C语言实现

//替换2个变量的值
void Swap(int *a,int *b){
    int temp = *a; 
    *a =*b;
    *b = temp;
}

//抉择排序
void SelectionSort(int *arr, int n) {
    //从数组起始地位开始，i初始化为0; 
    for (int i = 0; i < n - 1; i++) {
        // 假如以后地位为最小元素
        int min_index = i;
        //遍历待排序区间[i+1 - n-1]，如果存在更小的元素则更新min_index
        for (int j = i + 1; j < n; ++j) {
            if (arr[min_index] > arr[j]) {
                //循环查找最小值
                min_index = j;
            }
        }
        //查看min_index是否被更新过，是则将最小元素替换到地位i
        if(min_index!=i) {
            //应用替换，防止笼罩掉原先地位的元素
            Swap(&arr[i], &arr[min_index]);
        }
    }
}

Python实现

def SelectSort(arr):
    length = len(arr)
    for i in range(0,length-1):  
        min_tmp=i
        for j in range(i+1,length):  
            if arr[j]<arr[min_tmp]:
                min_tmp=j
        if min_tmp!=i:
            arr[i],arr[min_tmp] = arr[min_tmp],arr[i]