java实现选择排序_java选择排序

文章目录

1、 什么是选择排序？

 2、选择排序原理是什么？

  3、如何用java代码来实现呢？

4、用for循环嵌套实现选择排序 

5、时间复杂度

---

1、 什么是选择排序？

 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。（引用于百度百科）

 2、选择排序原理是什么？

如下图，该图是选择排序的效果动图。

  3、如何用java代码来实现呢？

我们可以这样思考：用第一个元素和每一个元素进行比较，从0索引开始，依次和后面元素比较，小的放前面，第一次完毕，最小值出现在最小索引处。

首先定义一个数组

 int[] arr = { 24, 69, 80, 57, 13 };

这个数组arr一共有5个元素，依次是24、67、80、57、13，我们需要让第一个元素24分别与其他元素进行比较，如果有比24还小的值，那么就交互位置。所以for循环i的初始值为1（因为是第一个元素与其他元素进行比较，所以第一个元素就不需要参与for循环，直接从下标1开始循环进行比较），for循环i的取值为从1到数组的长度5，因为i<arr.length，所以i是取不到5的，所以i的值只能是1、2、3、4，刚好是数组除第一个元素外其余元素的下标。

第一次比较

        //第一次比较
        int q=0;
        for (int i=1;i<arr.length;i++){
            if(arr[i]<arr[q]){
                //定义一个临时变量 把第大的值存放到临时变量 交换位置
                int temp=arr[q];
                arr[q]=arr[i];
                arr[i]=temp;
            }
        }
        //实现遍历
        System.out.print("[");
        for (int x = 0; x < arr.length; x++) {
            if (x == arr.length - 1) {
                System.out.println(arr[x] + "]");
            } else {
                System.out.print(arr[x] + ",");
            }
        }

第一次比较的结果 

 

 第一次比较结束，原本在数组最后一位的13被移动到了数组的第一个位置，接下来就开始第二次比较，那么for循环i的初始值就不再是1了，就应该从2开始遍历比较，需要在 int i=1后再加上1。

 //第一次比较
        int q=0;
        for (int i=1;i<arr.length;i++){
            if(arr[i]<arr[q]){
                int temp=arr[q];
                arr[q]=arr[i];
                arr[i]=temp;
            }
        }
        //第二次比较
        q=1;
        for (int i=1+1;i<arr.length;i++){
            if(arr[i]<arr[q]){
                int temp=arr[q];
                arr[q]=arr[i];
                arr[i]=temp;
            }
        }
        //实现遍历
        System.out.print("[");
        for (int x = 0; x < arr.length; x++) {
            if (x == arr.length - 1) {
                System.out.println(arr[x] + "]");
            } else {
                System.out.print(arr[x] + ",");
            }
        }

第二次比较结果 

 可以发现13、24这是数组中两个最小的值已经分别放到了第一、第二位了。

第三、第四次比较 

由于第三、第四次比较的原理与上面第一、第二次原理相同，第三次的比较结果就不再演示。

        //第一次比较
        int q=0;
        for (int i=1;i<arr.length;i++){
            if(arr[i]<arr[q]){
                int temp=arr[q];
                arr[q]=arr[i];
                arr[i]=temp;
            }
        }
        //第二次比较
        q=1;
        for (int i=1+1;i<arr.length;i++){
            if(arr[i]<arr[q]){
                int temp=arr[q];
                arr[q]=arr[i];
                arr[i]=temp;
            }
        }
        //第三次比较
        q=2;
        for (int i=1+2;i<arr.length;i++){
            if(arr[i]<arr[q]){
                int temp=arr[q];
                arr[q]=arr[i];
                arr[i]=temp;
            }
        }
        //第四次比较
        q=3;
        for (int i=1+3;i<arr.length;i++){
            if(arr[i]<arr[q]){
                int temp=arr[q];
                arr[q]=arr[i];
                arr[i]=temp;
            }
        }
        //实现遍历
        System.out.print("[");
        for (int x = 0; x < arr.length; x++) {
            if (x == arr.length - 1) {
                System.out.println(arr[x] + "]");
            } else {
                System.out.print(arr[x] + ",");
            }
        }

 第四次比较结果

 

4、用for循环嵌套实现选择排序 

 四次比较结束，数组已经由小到大依次进行排序，选择排序结束。但是这种一次一次的比较代码太过臃肿、重复率太高，开发过程中需要简洁开发，所以我们要对代码进行优化改进。就需要for循环的嵌套。我们可以发现一个规律，每多一次比较，q的值就会加1，所以我们在for循环外面再加上一次for循环，控制q的值，就能避免重复了。那么外层for循环的j的取值范围就是0到数组长度-1，因为数组长度为5，减去1后为4，但是j<4,是取不到4的，所以j的取值只能是0、1、2、3，刚好符合我们前面定义变量q的变化。

  // for循环嵌套实现
        for (int j=0;j<arr.length-1;j++){
            for (int i=1+j;i<arr.length;i++){
                if(arr[i]<arr[j]){
                    int temp=arr[j];
                    arr[j]=arr[i];
                    arr[i]=temp;
                }
            }
        }
        //实现遍历
        System.out.print("[");
        for (int x = 0; x < arr.length; x++) {
            if (x == arr.length - 1) {
                System.out.println(arr[x] + "]");
            } else {
                System.out.print(arr[x] + ",");
            }
        }

5、时间复杂度

第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。
共比较的次数是 (N - 1) + (N - 2) + ... + 1，求等差数列和，得 (N - 1 + 1)* （N -1）/ 2 = N^2 -1/ 2。舍去最高项系数，其时间复杂度为 O(N^2)。 

欢迎大家在评论区进行讨论并指正我的不足。