[数据结构与算法]选择排序实现

选择排序是排序算法中较为基础的排序算法。本人对选择排序的理解为：

存在一个数组，数组中存放着N个无序数。

实现：

??????? 在使用选择排序时，排序的每一趟最终目标是将某一个数和另外一个数进行位置交换，将其放在合适的位置，其他数的相对位置不变。（与冒泡不同在于，冒泡没有交换两个数的位置）

时间复杂度理解：

??????? 假设将数组中的每一个数对应二维表中的每一列，那么这个列表有N列，排序的每一趟当做列表中的每一行，那么这个列表有N-1行。之所以只有N-1行是当N-1个数字排序完毕，最后一个（第N个）数自然就在正确的位置。因此选择排序就够成了一张N*（N-1）的表格。由此可以看出从排序第一趟第一个数走到排序最后一趟（即N-1趟）最后一个数（第N个数），程序的时间复杂度为N^2-N.利用大O记法，可以记O(N^2),由此可知选择排序比较适用于数据量较小的双层循环。
?

在本人看来冒泡排序和选择排序有相同地方，当然也有一定差别。相同之处都存在元素大小比较，元素交换。不同之处在于，选择排序玩的是数组元素下标，冒泡排序玩的是数组元素。

以下是选择排序的java语言实现：

/*
选择排序（面向过程）
 */

public class sort01 {
    public static void main(String[] args) {
       int[] a={0,3,5,9,1,7,8,4,2};
        System.out.println("排序前：");
        show(a);
        System.out.println(" ");
        int[] b=sort(a);
        System.out.println("排序后");
        show(b);


    }

    public static int[] sort(int[] a){
        for (int i = 0; i < a.length - 1; i++) {//每找到一个最小值放到合适位置后，下次寻找从这个排好位置的数后面开始找
            int mindex=i;
            for (int j = i+1; j <a.length ; j++) {
                if(a[mindex]>a[j]){
                    mindex=j;
                }
            }
            int temp=a[i];
            a[i]=a[mindex];
            a[mindex]=temp;
            //此处的交换，指的是第一个元素和第一个以后比第一个还小的元素进行位置交换
        }
        return a;
    }

    public static void show(int[] a){
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
}

运行结果如下：

以下是C语言代码实现：

#include<stdio.h>

void sort(int a[],int b);

void main(){
    int i;
    int a[]={3,5,9,6,2,8,7};
    printf("排序前：");
    for(i=0;i<7;i++){
        printf("%d  ",a[i]);
    }
    printf("\n");
    printf("排序后：");
    sort(a,7);

}

void sort(int a[],int b){
    int i,j,temp,mindex;
    for(i=0;i<b-1;i++){
        mindex=i;
        for(j=i+1;j<b;j++){
            if(a[mindex]>a[j]){
               mindex=j;
            }
        }
        temp=a[i];
        a[i]=a[mindex];
        a[mindex]=temp;
    }
    for(i=0;i<b;i++){
        printf("%d  ",a[i]);
    }
}

其运行结果如下：

?

相关排序：

冒泡排序实现_lixxkv的博客-CSDN博客

以上是本人对选择排序算法的个人理解，不喜勿喷，感谢理解。