【排序算法详解】冒泡排序、选择排序

一、冒泡排序

先来看图

Image.png

算法原理

冒泡排序算法的原理如下：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

【Python 3】算法实现如下：

def bubble_sort(nums):
    for i in range(len(nums) - 1):  
    # 这个循环负责设置冒泡排序进行的次数
        for j in range(len(nums) - i - 1):  # j为列表下标
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums
 
print(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))
# 输出：[8, 12, 19, 22, 32, 33, 45, 97]

算法分析

• 冒泡排序最好的时间复杂度为 O(n)

• 冒泡排序总的 平均时间复杂度 为

  

【Java_Code】如下：

// ---正确实例
import java.util.Scanner;

public class BulleSorted {

    // logic to sort the elements
    public static void bubble_srt(int array[]) {
        int n = array.length;
        int k;
        for (int m = n; m >= 0; m--) {
            for (int i = 0; i < n - 1; i++) {
                k = i + 1;
                if (array[i] > array[k]) {
                    int temp;
                    temp = array[i];
                    array[i] = array[k];
                    array[k] = temp;
                }
            }
            printNumbers(array);
        }
    }

    private static void swapNumbers(int i, int j, int[] array) {

        int temp;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private static void printNumbers(int[] input) {

        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ", ");
        }
        System.out.println("\n");
    }

    public static void main(String[] args) {
        System.out.println("对原始数组进行冒泡排序；" +'\n');
        int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
        bubble_srt(input); 
               
        // 对输入的数组进行转化
        System.out.println("请输入您要冒泡排序的数组：" +'\n');
        Scanner sc = new Scanner(System.in);
        String inputString = sc.nextLine();
        String stringArray[] = inputString.split(",");

        int num[] = new int[stringArray.length];
        for (int i = 0; i < stringArray.length; i++) {
              num[i] = Integer.parseInt(stringArray[i]);
        }
        bubble_srt(num);
    }
}

【技能点】：在冒泡排序算法中，主要思想是让数组当中相邻的两个数进行比较，数组当中比较小的数值向下沉，数值比较大的向上浮！外层for循环控制循环次数，内层for循环控制相邻的两个元素进行比较。

【输出结果如下】：

Image.png image2.png

---

二、选择排序

能通过看图明白，那就不需要看文字描述了。

Image-选择排序.png

工作原理

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
【Python3】

def selection_sort(list2):
  for i in range(0, len (list2)-1):
    min_ = i
    for j in range(i + 1, len(list2)):
      if list2[j] < list2[min_]:
        min_ = j
    list2[i], list2[min_] = list2[min_], list2[i]  

算法性能

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

算法优化

【思想】：在每次比较中，将本次中最小的元素放在本次比较的第1个位置，所以选择排序的每次比较只需要交换一次即可，只要找到本次比较中最小的元素和本趟比较中第一位置的元素交换即可。
【Java_Code】如下：

import java.util.Scanner;

public class SelectionSort{
    public static int[] selectionSroted(int[] array){
        for(int i = 0;i < array.length - 1; i++){
            int index = i;
            for(int j = i + 1;j < array.length ; j++){
                if (array[j]<array[index])
                    index = j;

            int smallerNum = array[index];
            array[index] = array[i];
            array[i] = smallerNum;  
            }
        }
        return array;
    }
    private static void printNumbers(int[] input) {
        System.out.println("开始数组排序..." +'\n');
        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ", ");
        }
        System.out.println("\n");
    }

    public static void main(String[] args) {
        int[] array_one = {12,324,45646,678,6,1,99,100};
        int[] array_two = selectionSroted(array_one);
        printNumbers(array_two);

        System.out.println("请输入您要排序的数组：" +'\n');
        Scanner sc = new Scanner(System.in);
        String inputString = sc.nextLine();
        String stringArray[] = inputString.split(",");

        int num[] = new int[stringArray.length];
        for (int i = 0; i < stringArray.length; i++) {
              num[i] = Integer.parseInt(stringArray[i]);
        }
        int[] array_three = selectionSroted(num);
        printNumbers(array_three);
    }
}

结果如下.png