20190706 数据结构和算法之八大排序算法

[xinrong2019]

交换排序：

• 冒泡排序

• 快速排序

插入排序

• 直接插入排序

• 希尔排序

选择排序

• 简单选择排序

• 堆排序

归并排序

基数排序

[xinrong2019]

冒泡排序

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr=new int[] {5,7,2,9,4,1,0,5,7};
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //冒泡排序
    /**
     * 5,7,2,9,4,1,0,5,7        共需要比较length-1轮
     * 5,7,2,9,4,1,0,5,7    
     * 5,2,7,9,4,1,0,5,7
     * 5,2,7,4,1,0,5,7,9
     * 2,5   
     */
    public static void bubbleSort(int[]  arr) {
        //控制共比较多少轮
        for(int i=0;i<arr.length-1;i++) {
            //控制比较的次数，前i次已经比较过了，所以不需要比较
            for(int j=0;j<arr.length-1-i;j++) {
                if(arr[j]>arr[j+1]) {
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }

    }

}

[xinrong2019]

快速排序

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[] {3,4,6,7,2,7,2,8,0,9,1};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int start,int end) {
        if(start<end) {
            //把数组中的第0个数字做为标准数
            int stard=arr[start];
            //记录需要排序的下标
            int low=start;
            int high=end;
            //循环找比标准数大的数和比标准数小的数
            while(low<high) {
                //右边的数字比标准数大
                while(low<high&&stard<=arr[high]) {
                    high--;
                }
                //使用右边的数字替换左边的数
                arr[low]=arr[high];
                //如果左边的数字比标准数小
                while(low<high&&arr[low]<=stard) {
                    low++;
                }
                arr[high]=arr[low];
            }
            //把标准数赋给低所在的位置的元素，高也行，此时位置重合
            arr[low]=stard;
            //处理所有的小的数字
            quickSort(arr, start, low);
            //处理所有的大的数字
            quickSort(arr, low+1, end);
        }
    }

}