java 排序算法

冒泡排序

冒泡排序的基本思想是：对比相邻的元素值，如果满足条件就交换元素值，把较小的元素值移动到数组前面，把大的元素值移动到数组后面（也就是交换两个元素的位置），这样数组元素就像气泡一样从底部上升到顶部。

冒泡排序的算法比较简单，排序的结果稳定，但时间效率不太高。
Java 中的冒泡排序在双层循环中实现，其中外层循环控制排序轮数，总循环次数为要排序数组的长度减 1。而内层循环主要用于对比相邻元素的大小，以确定是否交换位置，对比和交换次数依排序轮数而减少。

 public void bubbleSort(){
        int[] score = {77,90,68,59,80};
        System.out.println("通过冒泡排序方法对数组进行排序：");
        for (int i = 0; i < score.length - 1; i++) {
            // 比较相邻两个元素，较大的数往后冒泡
            for (int j = 0; j < score.length - 1 - i; j++) {
                if (score[j] > score[j + 1]) {
                    int temp = score[j + 1]; // 把第一个元素值保存到临时变量中
                    score[j + 1] = score[j]; // 把第二个元素值转移到第一个元素变量中
                    score[j] = temp; // 把临时变量（第一个元素的原值）保存到第二个元素中
                }
                System.out.print(score[j] + " "); // 对排序后的数组元素进行输出
            }
            System.out.print("【");
            for (int j = score.length - 1 - i; j < score.length; j++) {
                System.out.print(score[j] + " ");
            }
            System.out.println("】");
        }
    }

输出结果

通过冒泡排序方法对数组进行排序：
77 68 59 80 【90 】
68 59 77 【80 90 】
59 68 【77 80 90 】
59 【68 77 80 90 】

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进，是一种排序执行效率很高的排序算法。

快速排序的基本思想是：通过一趟排序，将要排序的数据分隔成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此使整个数据变成有序序列。

具体做法是：假设要对某个数组进行排序，首先需要任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它的前面，所有比它大的数都放到它的后面。这个过程称为一趟快速排序；递归调用此过程，即可实现数据的快速排序。

    public int getMiddle(int[] list,int low,int high){
        int tmp = list[low]; // 数组的第一个值作为中轴（分界点或关键数据）
        while (low < high){
            //找到小于临界值tmp的list[high]
            while (low < high && list[high] > tmp){
                high--;
            }
            //找到后 将 list[high] 的值赋给list[low]
            list[low] = list[high];
            while (low < high && list[low] < tmp){
                low++;
            }
            list[high] = list[low];
        }
        list[low] = tmp;
        return low;  // 返回中轴的位置
    }

    public void unckSort(int[] list,int low,int high){
        if (low < high){
            int middle = getMiddle(list,low,high);
            unckSort(list,low,middle - 1);
            unckSort(list,middle + 1,high);
        }
    }

    public void quickSort(){
        int[] number={13,15,24,99,14,11,1,2,3};
        if (number.length > 0){
            unckSort(number,0,number.length - 1);
        }
        for (int val:number){
            System.out.print(val + " ");
        }
    }

选择排序

选择排序是指每一趟从待排序的数据元素中选出最大（或最小）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完

public void selectSort(){
        int[] number={13,15,24,99,4,1};
        String end="\n";
        int index;
        for(int i=1;i<number.length;i++)
        {
            index=0;
            for(int j=1;j<=number.length-i;j++)
            {
                if(number[j]>number[index])
                {
                    index=j;    //查找最大值
                }
            }
            end=number[index]+" "+end;    //定位已排好的数组元素
            int temp=number[number.length-i];
            number[number.length-1]=number[index];
            number[index]=temp;
            System.out.print("【");
            for(int j=0;j<number.length-i;j++)
            {
                System.out.print(number[j]+" ");
            }
            System.out.print("】"+end);
        }
    }

//输出结果：
【13 15 24 1 4 】99 
【13 15 4 1 】24 99 
【13 1 4 】15 24 99 
【4 1 】13 15 24 99 
【1 】4 13 15 24 99 

直接插入排序

直接插入排序的基本思想是：将 n 个有序数存放在数组 a 中，要插入的数为 x，首先确定 x 插在数组中的位置 p，然后将 p 之后的元素都向后移一个位置，空出 a(p)，将 x 放入 a(p)，这样可实现插入 x 后仍然有序。

 public void Insertsort() {
        int[] number = { 13, 15, 24, 99, 4, 1 };
        System.out.println("排序前：");
        for (int val : number) { // 遍历数组元素
            System.out.print(val + " "); // 输出数组元素
        }
        int temp, j;
        for (int i = 1; i < number.length; i++) {
            temp = number[i];
            for (j = i - 1; j >= 0 && number[j] > temp; j--) {
                number[j + 1] = number[j];
            }
            number[j + 1] = temp;
        }
        System.out.println("\n排序后：");
        for (int val : number) { // 遍历数组元素
            System.out.print(val + " "); // 输出数组元素
        }
    }