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

TheLudGamer · 发表于 2021-11-14 20:24

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

Arzie100 · 发表于 2021-11-14 20:32

修改点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 · 发表于 2021-11-14 20:38

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

闲鱼技术01 · 发表于 2021-11-14 20:41

厉害！

TheLudGamer · 发表于 2021-11-14 20:49

给你改好了
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 · 发表于 2021-11-14 20:54

@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 · 发表于 2021-11-14 21:01

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

KaaPexei · 发表于 2021-11-14 21:07

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

NoiseFloor · 发表于 2021-11-14 21:07

你这个是错的，你没有考虑到这样一种情况：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位置）

		自动登录	找回密码
密码			立即注册