【大话数据结构&算法】直接选择排序

港控/mmm° 2022-07-19 00:19 192阅读 0赞

选择类排序的主要动作是“选择”，**直接选择排序采用最简单的选择方式，从头至尾顺序扫描序列，找出最小的一个记录，和第一个记录交换，接着从剩下的记录中继续这种选择和交换，最终使序列有序**。

--------------------

**直接选择排序算法思想（以从小到大为例）：**

> 1、从第一个元素开始，选出一个最小的元素与第一个元素互换；  
> 2、继续从第二个元素开始，向后选出最小的元素，与第二个元素互换；  
> 3、依次循环执行，直到最大的元素放在了最后一个位置上，排序完成。

--------------------

**直接选择排序基本算法实现如下：**

void selectSort1(int[] a, int n){
           int temp;
           for(int i = 0;i < n;i++){
                 for(int j = i + 1;j < n;j++){
                       //从第一个元素开始依次与后面的元素进行比较
                       if(a[i] > a[j]){
                            temp = a[i];
                            a[i] = a[j];
                            a[j] = temp;
                      }
                }
          }
        }

--------------------

**改进直接选择排序：**

> 在排序中我们应该尽量避免较多和元素互换的操作，而这里每比较一次，如果遇到更小的，就要进行一次元素互换。为了减少元素互换操作，我们可以在每次比较之后不直接进行交换，将较小的元素的位置序号记录下来，这样一趟比较之后，就会得到最小的元素的位置，如果最小值的位置发生了改变，再将该位置的元素与第一个元素互换，以此类推，这样，每一趟比较完成之后最多只需执行一次元素互换。

--------------------

**java代码实现如下：**

public class SelectSort {
    
           public static void main(String[] args) {
                 int[] a = {
       5,3,9,6,8,1,0,2};
                 selectSort1(a,8);
                 for (int i = 0; i < a.length; i++) {
                      System. out.println(a[i]);
                }
                System. out.println("*********" );
                 int[] b = {
       5,3,9,6,8,1,0,2};
                 selectSort2(b, 8);
                 for (int i = 0; i < b.length; i++) {
                      System. out.println(b[i]);
                }
          }
    
          //直接选择排序基本实现
           public static void selectSort1(int[] a, int n){
                 int temp;
                 for(int i = 0;i < n;i++){
                       for(int j = i + 1;j < n;j++){
                             //从第一个元素开始依次与后面的元素进行比较
                             if(a[i] > a[j]){
                                  temp = a[i];
                                  a[i] = a[j];
                                  a[j] = temp;
                            }
                      }
                }
          }
    
           //改进直接选择排序
           public static void selectSort2(int[] a, int n){
                 int min,temp;//记录最小值的位置
                 for(int i = 0;i < n;i++){
                       //用来记录每一趟比较的最小值的位置
                      min = i;
                       for(int j = i + 1;j < n;j++){
                             //如果遇到更小的值，则更新最小值位置记录
                             if(a[j] < a[min]){
                                  min = j;
                            }
                      }
                       //如果最小值的位置发生变化，则在最后执行一次元素互换
                       if(min != i){
                            temp = a[i];
                            a[i] = a[min];
                            a[min] = temp;
                      }
                }
          }
    
    }

--------------------

**时间复杂度O(n2)\{n的平方\}，空间复杂度O(1)。**