算法-选择排序-如何优化？

TheLudGamer

换了第一个之后另外一个下标得考虑调整

Arzie100

修改点1：取消break条件（这个完全错误），通过缩短循环长度改进
修改点2：每次找min和max前，如果arr[min]>arr[max]，先交换

修改后算法：
void ssortx(int *arr, int len)
{
    for (int i = 0; i < len - 1 - i; i++)
    {
        int min = i;
        int max = len - 1 - i;
        if (arr[min] > arr[max]) swap(arr, min, max);
        for(int j = i + 1; j < len - 1 - i; j++)
        {
            if (arr[j] < arr[min]) min = j;
            if (arr[j] > arr[max]) max = j;
        }
        swap(arr, i, min);
        swap(arr, len - 1 - i, max);
    }
}

执行结果：
12 45 6 1 6521 7 861 2376 73 2 4 1
1 1 2 4 6 7 12 45 73 861 2376 6521

执行10w次，速度显著提高
ps：等其他人试试

RedZero9

看我评论修改后的算法，这个可以排序出正确结果了

闲鱼技术01

厉害！

TheLudGamer

给你改好了
def selection_sort2(data_list):
    count = 0
    length = len(data_list)
    for i in range(length -1):
        print(data_list) #打印每一次选择后的结果
        min_index = i #存储最小值的下标
        max_index = length - i -1 #最大值的下标，以便最后交换
        # 退出条件挪上面
        if min_index +1 == max_index:
            break
        # 修改循环的条件
        for j in range(i,length - i):
            count +=1
            if data_list[min_index] > data_list[j]:
                min_index = j
            if data_list[max_index] < data_list[j]:
                max_index = j
        #前面的数据与最小值交换
        if min_index != i: #说明需要交换，否则不需要自己自己交换
            tmp = data_list
            data_list = data_list[min_index]
            data_list[min_index] = tmp
        # 判断有没有最大值的下标正好是i的情况
        if max_index == i:
            max_index = min_index
        #后面的数据与最大值交换
        if max_index != length - i -1: #说明需要交换，否则不需要自己与自己交换
            tmp = data_list[length - i -1 ]
            data_list[length -i -1 ] = data_list[max_index]
            data_list[max_index] = tmp
    # 最后要进行比较 arr.length /2 -1 和arr.length /2下标的值
    midIndex =length//2
    if data_list[midIndex-1] > data_list[midIndex]:
        tmp = data_list[midIndex - 1]
        data_list[midIndex - 1] = data_list[midIndex]
        data_list[midIndex] = tmp
    print(f"总循环次数为 {count}")
    return data_list

acecase

@fiofio 看着你改的 python 版本
def select(arr):
    temp = arr
    left = 0
    right = len(temp) - 1
    while left < right:
        p = left
        m = len(temp) - 1 - left
        for j in range(left + 1, len(temp) - left):
            if temp[j] < temp[p]:
                p = j
            if temp[j] > temp[m]:
                m = j
        swap(temp, left, p)
        swap(temp, len(temp) - 1 - left, m)
        left += 1
        right -= 1
    return temp

快很多

闲鱼技术01

思路没问题，但是代码有bug

KaaPexei

两个错误，break条件那里，当数组是奇数项时，break不出来，应该改成minindex+1==maxindex | minindex==maxindex。第二个是上面评论也说到的，在进入第二层循环前先比较minindex和maxindex处的值，不然算法错误。答主这个算法写完没测试吧，写一个datachecker，随机生成数组排序然后循环几万次测试

NoiseFloor

你这个是错的，你没有考虑到这样一种情况：arr刚好是逆序[9,8,7,6,5,4,3,2,1]，你的算法的结果是[1 2 3 4 9 5 6 7 8]，你的例程里的内循环都是从left + 1 开始的，忽略了left可能是最大值的情况，第一次swap会将正确的最大值arr[left]从left位置放到最后的正确位置，然而你的第二次swap会将最大值从正确位置又移向了错误位置（也就是j，内循环的left+1位置）