直接选择排序和冒泡排序

一.直接选择排序(Straight Selection Sort)

1、直接选择排序的基本思想

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
　
①初始状态： 无序区为R[1…n]，有序区为空。
②第1趟排序
　在无序区R[1…n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1…1]和R[2…n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
　　……
③第i趟排序
　　第i趟排序开始时，当前有序区和无序区分别为R[1…i-1]和Ri…n。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1…i]和R[i+1…n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
　这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

2.代码实现：

import java.util.Arrays;
public class SortTest {
    public static void main(String[] args) {
        // 定义需要升序排序的数组arr
        int [] arr={8,4,15,2,1};
        // 对数组升序排序
        for (int i = 0; i < arr.length - 1; i++) {
            int  min = i;
            // 找出第i个元素之后最小值的索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            // 交换最小值
            if (min != i) {
                int tmp = arr[min];
                arr[min] = arr[i];
                arr[i] = tmp;
            }
        }
        // 输出排序后的数组，使用java.util.Arrays包下的Arrays类调用toString方法可以打印数组元素
        System.out.println(Arrays.toString(arr));
    }
}

输出结果：

[1, 2, 4, 8, 15]

排序过程：

原始数组：8 4 15 2 1
第一次排序结果：1 4 15 2 8。排好了第1位。
第二次排序结果：1 2 15 4 8。排好了第2位。
第三次排序结果：1 2 4 15 8。排好了第3位。
第四次排序结果：1 2 4 8 15。排好了第4位。

3.直接选择排序de稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，
若经过排序，这些记录的相对次序保持不变，
即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，
则称这种排序算法是稳定的；否则称为不稳定的。

所以选择排序是一个不稳定的排序算法。

4.时间复杂度分析

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

虽然选择排序和冒泡排序的时间复杂度一样，但实际上，选择排序进行的交换操作很少，最多会发生 N - 1次交换。
而冒泡排序最坏的情况下要发生N^2 /2交换操作。从这个意义上讲，交换排序的性能略优于冒泡排序。
而且，交换排序比冒泡排序的思想更加直观。

5.例题：使用直接选择排序(按升序)对给定的数组排序，并输出每次排序结果以及排序完成后的数组，具体要求如下

接收给定的数据（如：4 88 43 43 98 #…，其中第一个数代表数组长度，其余数代表数组元素，# 号用于终止接收数据），遇到 # 号终止接收；
创建数组，使用直接选择排序(按升序)对给定的数组排序，并输出每次排序结果以及排序完成后的数组。

注意：数字分隔符为空格。

import java.util.Scanner;
import java.util.Arrays;

public class SortTest {
    public static void main(String[] args) {
        // 请在Begin-End间编写代码
        /********** Begin **********/
        // 接收给定数据
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        // 定义数组
        int a[] = new int [n];
        // 给数组赋值
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        // 使用直接选择排序法对数组升序排序，并输出每次排序的结果
        int count=0;
        for(int i=0;i<a.length-1;i++){
            int min =i;
            for(int j=i+1;j<a.length;j++){
                if(a[min]>a[j]){
                    min = j;                    
                }
            }
            if(min!=i){
                int t = a[min];
                a[min]=a[i];
                a[i]=t;              
            }
            count++;
            System.out.println("第"+count+"次排序:"+Arrays.toString(a));
        }
        // 输出排序后的数组
        System.out.println("排序后的结果为："+Arrays.toString(a));
        /********** End **********/
    }
}

测试输入：9 1 6 53 54 2 89 54 90 21 #

—— 预期输出 ——
第1次排序:[1, 6, 53, 54, 2, 89, 54, 90, 21]
第2次排序:[1, 2, 53, 54, 6, 89, 54, 90, 21]
第3次排序:[1, 2, 6, 54, 53, 89, 54, 90, 21]
第4次排序:[1, 2, 6, 21, 53, 89, 54, 90, 54]
第5次排序:[1, 2, 6, 21, 53, 89, 54, 90, 54]
第6次排序:[1, 2, 6, 21, 53, 54, 89, 90, 54]
第7次排序:[1, 2, 6, 21, 53, 54, 54, 90, 89]
第8次排序:[1, 2, 6, 21, 53, 54, 54, 89, 90]
排序后的结果为：[1, 2, 6, 21, 53, 54, 54, 89, 90]

二.冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

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

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

2.代码实现：

import java.util.Arrays;
public class SortTest {
    public static void main(String[] args) {
        // 定义需要升序排序的数组arr
        int [] arr={8,4,15,2,1};
        // 对数组升序排序
        for(int i =0;i<arr.length-1;i++) {       // 外循环为排序趟数，n个数进行n-1趟
     
            for(int j=0;j<arr.length-1-i;j++) {    //内循环为每趟比较的次数，第i趟比较n-i次
                if(arr[j]>arr[j+1]) {       //相邻元素比较，若逆序则交换（升序为左大于右，降序反之）
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        // 输出排序后的数组，使用java.util.Arrays包下的Arrays类调用toString方法可以打印数组元素
        System.out.println(Arrays.toString(arr));
    }
}

输出结果：

[1, 2, 4, 8, 15]

排序过程：

原始数组：8 4 15 2 1
第一次排序结果：4 8 2 1 15。排好了最后1位。
第二次排序结果：4 2 1 8 15。排好了倒数第2位。
第三次排序结果：2 1 4 8 15。排好了倒数第3位。
第四次排序结果：1 2 4 8 15。排好了倒数第4位。

3.冒泡排序算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

4.时间复杂度

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

综上，因此冒泡排序总的平均时间复杂度为 O(n²)

三.直接选择排序和冒泡排序的优缺点

1.冒泡排序

优点是比较简单，空间复杂度较低，是稳定的；缺点是时间复杂度太高，效率慢。

2.选择排序

优点是一轮比较只需要换一次位置；缺点是效率慢，不稳定。

四.总结：

数组全部输出

可以使用java.util.Arrays包下的Arrays类调用toString方法可以打印数组元素 System.out.println(Arrays.toString(arr));

1 问题描述
给定一个可排序的n元素序列（例如，数字、字符和字符串），将它们按照非降序方式重新排列。

2 解决方案
2.1 选择排序原理简介
选择排序开始的时候，我们从第一个元素开始扫描整个列表，找到它的最小元素，然后和第一个元素交换，将最小元素和第一个元素交换位置；然后，我们从第二个元素开始扫描剩下的n-1个元素，找到这n-1个元素中的最小元素，将最小元素和第二个元素交换位置；然后从第三个元素开始扫描…一般来说，就是从第i个元素开始扫描，找到第n-i+1个元素中的最小元素，将最小元素与第i个元素交换位置。这样，在进行n-1次遍历后，该列表就排好序了。

package com.liuzhen.chapterThree;

public class SelectionSort {
    
    public static void getSelectionSort(int[] a){
        int min = 0;     //用于存放n-i序列中最小元素序号
        int temp = 0;    //交换数组元素值的中间变量
        //打印输出未排序前数组序列
        System.out.print("排序前：          ");
        for(int p = 0;p < a.length;p++)
            System.out.print(a[p]+"\t");
        System.out.println();
        
        for(int i = 0;i < a.length-1;i++){
            min = i;
            for(int j = i+1;j < a.length;j++){
                if(a[j] < a[min])
                    min = j;
            }
            //交换a[i]和a[min]的值
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
            //打印输出每一次选择排序结果
            System.out.print("排序第"+(i+1)+"趟：");
            for(int p = 0;p < a.length;p++)
                System.out.print(a[p]+"\t");
            System.out.println();
        }
    }
    
    public static void main(String args[]){
        int[] a = {89,45,68,90,29,34,17};
        getSelectionSort(a);
    }
}

运行结果：

排序前：   89    45    68    90    29    34    17    
排序第1趟：17    45    68    90    29    34    89    
排序第2趟：17    29    68    90    45    34    89    
排序第3趟：17    29    34    90    45    68    89    
排序第4趟：17    29    34    45    90    68    89    
排序第5趟：17    29    34    45    68    90    89    
排序第6趟：17    29    34    45    68    89    90

2.3 冒泡排序原理简介
我们从列表的第一个元素开始，比较列表中相邻的两个元素，如果第一个元素大于第二元素，则交换这两个元素的位置，否则就从第二个元素位置开始重复上一步操作。重复多次以后，最大的元素就“沉到”列表的最后一个位置。这样一直做，直到n-1遍以后，该列表就排好序了。

package com.liuzhen.chapterThree;

public class BubbleSort {
    
    public static void getBubbleSort(int[] a){
        int temp;      
        //打印输出未排序前数组序列
        System.out.print("排序前：          ");
        for(int p = 0;p < a.length;p++)
            System.out.print(a[p]+"\t");
        System.out.println();            
        for(int i = 0;i < a.length-1;i++){            
            for(int j = 0;j < a.length-1-i;j++){
                if(a[j+1] < a[j]){
                    //交换a[j]和a[j+1]的值
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
            //打印输出每一次选择排序结果
            System.out.print("排序第"+(i+1)+"趟：");
            for(int p = 0;p < a.length;p++)
                System.out.print(a[p]+"\t");
            System.out.println();
        }
    }
    
    public static void main(String args[]){
        int[] a = {89,45,68,90,29,34,17};
        getBubbleSort(a);
    }
}

运行结果：

排序前：   89    45    68    90    29    34    17    
排序第1趟：45    68    89    29    34    17    90    
排序第2趟：45    68    29    34    17    89    90    
排序第3趟：45    29    34    17    68    89    90    
排序第4趟：29    34    17    45    68    89    90    
排序第5趟：29    17    34    45    68    89    90    
排序第6趟：17    29    34    45    68    89    90

一 简单选择排序：
排序过程：
(1)首先通过n-1次比较，找出n个数中最小的，使它与第一个书交换——第一趟选择排序，这时候最小的元素就在第一个位置了。
(2)再通过n-2次比较，从剩余的n-1个数中找出次小的并与第二个数交换将它放在第二个元素位置——第二趟选择排序。
(3)重复上述过程，经过n-1次排序后，排序结束。
例如我们对{3,5,7,8,9,6,2,1,4}从小到大排序
第一趟：通过8次比较，找出最小的数1，让他与第一个元素交换，这时候1就调到了第一个元素位置。
这时候序列式{1,3,5,7,8,9,6,2,4}
第二趟：不对1进行比较，比较后面的7个数，将2调到了第二个元素位置。
重复以上操作，最后就实现了从小到大的排序。、
具体代码实现：

#include <iostream>

using namespace std;

int main()
{
    int a[101];
    int k,n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n-1;i++)
    {   k=i;
        for(int j=i+1;j<=n;j++)
            if(a[k]>a[j])k=j;
            if(k!=i)
            {
                int t;
                t=a[i];
                a[i]=a[k];
                a[k]=t;
                }
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}

运行结果

程序过程；
首先i=1的时候：5跟4比，4比5小，4和5交换位置，然后4跟3比，3比4小，交换位置，然后3跟2比。2比3小，交换位置，2跟1比，2比1大，交换位置，第一趟排序结束，得到1 5 4 3 2的顺序。
i=2的时候：5跟4比，4跟3比，3跟2比，结束后得到1 2 5 4 3的顺序。
重复以上过程最后i=4的时候 前面3个数是1 2 3 后面是5和4，5和4比，4比5小，交换位置，排序结束得到1 2 3 4 5.
二 冒泡排序
排序过程：
(1)比较第一个数与第二个数，若为逆序a[0]>a[1]，则交换；然后比较第二个数与第三个数；以此类推，直至第n-1个数和第n个数比较为止——第一趟冒泡排序，结果最大的数被安置在最后一个元素位置上。
(2)对前n-1个数进行第二趟排序，结果次大的数被安置在第n-1个元素位置。
(3)重复上述过程，共经过n-1趟冒泡排序后，排序结束。
例如：
设n=6，本例a[0]不用，只用a[1]~a[6]，定义数组长度为7，即a[7]。

以上是形象的排序过程。
程序实现：

#include <iostream>

using namespace std;

int main()
{
    int a[7];


    for(int i=1;i<=6;i++)
    cin>>a[i];
    for(int i=1;i<=6-1;i++)
        for(int j=1;j<=6-i;j++)
            if(a[j]>a[j+1])
            {   int t;
                t=a[j];
                a[j]=a[j+1];

运行结果：

程序过程
第一趟：6与8比，8比6大，不交换位置，然后8与4比；8比4大，交换位置，然后8与9比，8比9小，不交换位置，然后9与2比，交换位置，然后9与3比交换位置，最终最大的数9跑到了最后一个位置。
第二趟：上一趟排序后的顺序为6 4 8 2 3 9 因为9已经是在最后一个位置了 所以第二趟进行四次比较就行 最终将次大的数8移到倒数第二个位置。
重复以上操作，得到顺序2 3 4 6 8 9，排序结束。