基础练习 数列排序

时间限制:1.0s 内存限制:512.0MB

问题描述
给定一个长度为n的数列,将这个数列按从小到大的顺序排列。1<=n<=200
输入格式
第一行为一个整数n。
第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。
输出格式
输出一行,按从小到大的顺序输出排序后的数列。
样例输入
5
8 3 6 4 9
样例输出
3 4 6 8 9

import java.util.Scanner;
public class Sorting {

    public static void main(String[] args) {
        
        int[] sortArr;
        int n;
        Scanner sn = new Scanner(System.in);
        n = sn.nextInt();
        sortArr = new int[n];
        for(int i = 0;i < n;i ++){
            sortArr[i] = sn.nextInt();
        }
        
        //使用冒泡排序
        //bubbleSort(sortArr);
        
        //使用选择排序
        //selectionSort(sortArr);
        
        //使用快速排序
        quickSort(sortArr,0,sortArr.length - 1);
        
        for(int i: sortArr){                 //使用foreach循环遍历并输出数组元素
            System.out.print(i + " ");
        }
    }
    
    //冒泡排序
    public static void bubbleSort(int[] sortArr) {
        int minIndex;
        for(int i = 0;i < sortArr.length-1;i ++){
            for(int j = i + 1;j < sortArr.length;j ++){
                /*比较相邻的两个数,sortArr[i] > sortArr[j],我们就交换。
                 * 如果想从大到小输出,只需要成"<" 符号。
                 * */
                if(sortArr[i] > sortArr[j]){                
                    sortArr[i] = sortArr[i] ^ sortArr[j];
                    sortArr[j] = sortArr[j] ^ sortArr[i];
                    sortArr[i] = sortArr[i] ^ sortArr[j];
                }
            }
        }
    }
    
    //选择排序
    public static void selectionSort(int[] sortArr){
        int minIndex;
        if(sortArr == null && sortArr.length == 0 ){     //当数组为空时,就不用排序
            return;
        }
        for(int i = 0;i < sortArr.length;i ++){
            minIndex = i;                               //将第一个数设为最小元素
            for(int j = i+1;j < sortArr.length;j ++){
                //如果找到比我们假设的最小元素还小的元素,就保留它的下标,直到找到真正最小的元素
                if(sortArr[minIndex] > sortArr[j]){        
                    minIndex = j;
                }
            }
            if(i != minIndex){                            //当我们假设的最小元素就是最小元素时,我们就可以不用交换值了
            sortArr[i] = sortArr[i] ^ sortArr[minIndex];
            sortArr[minIndex] = sortArr[minIndex] ^ sortArr[i];
            sortArr[i] = sortArr[i] ^ sortArr[minIndex];
            }
        }
    }
    
    //快速排序
    public static void quickSort(int[] sortArr,int start,int end){
        if(start < end){
            int mid = partition(sortArr,start,end);            //调用分区方法,将数组进行分区
            quickSort(sortArr, start, mid-1);                //对左分区进行排序
            quickSort(sortArr, mid+1, end);                    //对右分区进行排序
        }
    }
    //分区方法
    public static int partition(int[] sortArr,int start,int end){
        int tmp = sortArr[start];                            //使第一个数为基准值,并保存
        while(start != end){                                //当开始位置与结束位置相同时,便不用进行比较了
            while(start < end && sortArr[end] >= tmp){        //从右边开始扫描,直到找到第一个比基准值大的数
                end --;
            }
            sortArr[start] = sortArr[end];                    //将end位置假设为空出位置
            while(start < end && sortArr[start] <= tmp){    //从左边开始扫描,直到找到第一个比基准值小的数
                start ++;
            }
            sortArr[end] = sortArr[start];                    //将start位置假设为空出位置
        }
        sortArr[start] = tmp;                                //把基准数放置在最终位置
        return start;                                        //带回基础数下标
    }

}

注解:

冒泡排序思路:每次比较相邻的两个数,如果比它大(小)就交换。一直到数组最大下标。因为这种排序像冒泡泡一样,
所以被称为冒泡排序。
选择排序思路:假设一个最大(最小)值,依次比较,当遇到一个比它大(小)的数就交换。因为他是选择一个假定值
进行比较排序,所以被称为选择排序。
快速排序思路:快速排序稍微复杂点,首先将一个数组进行分区,假定一个基准数并保存;一般取第一个数为基准数。依次从右至左扫描;遇到第一个比它大(小)的数就将基准数的数组位置覆盖,并空出自己的位置。再从左至右扫描,遇到第一个比它小(大)的数就覆盖空出的位置。直到左右两边的标识相等,便结束循环;并进行下一次排序,直到递归结束。
Last modification:March 17th, 2019 at 01:31 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment