三种排序算法 归并、快排、冒泡

2020/02/10 Java

快排

把第一个数字当成标杆,以这个标杆把小于和大于他的部分分开。之后在对两部分做快排。

package sort;

import java.util.TreeMap;

public class QuickSort {
    // 思想是以 start 为中心,把数组分为两部分,左边都比 start 小,右边都比 start 大,start 在中间。start 位置的数一直再跟着移动
    // 然后在继续把数组二分,以新的 start 分成两个数组,对每个数组在快排
    public void sort(int[] nums,int start,int end){
        if(start>=end) return;
        int begin = start;
        int last = end;
        int compare = nums[start];
        while(start<end){
            while(start<end && nums[end]>=compare){ //后面先往前推,找到比标准值小的
                end--;
            }
            if(start<end){
                nums[start++] = nums[end];//把小的移到前面,nums[end] 就作为下一次移过来的地方
            }
            while(start<end && nums[start]<=compare){//往后面推,找到比标准值大的,nums[start] 就作为下次移过的地方
                start++;
            }
            if(start<end){
                nums[end--] = nums[start];
            }
        }
        nums[start] = compare;// 把分割线填上。
        sort(nums,begin,start-1); //对低位排序
        sort(nums,start+1,last); //对高位排序
    }

    public static void main(String[] args) {

        TreeMap<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("c",0);
        treeMap.put("d",1);
        System.out.println(treeMap.firstKey());


        int[] array = {5,4,6,8,1,3};
        new QuickSort().sort(array,0,array.length-1);
        for(int a:array){
            System.out.print(a+" ");
        }
    }
}

归并排序

一直对数组拆分,直到两两比较,这样可以直接两个部分都是有序的,可以很快生成新的有序字段,之后在一步步组合起来。

package sort;

public class MergeSort {
    public void mergeSort(int[] array,int begin, int end){
        if(begin==end) return;
        int mid = begin+(end-begin)/2;
        mergeSort(array,begin,mid);
        mergeSort(array,mid+1,end);
        sort(array,begin,mid,end);
    }
    public void sort(int[] array,int begin,int mid,int end){
        int[] copy = new int[end-begin+1];
        int start1 = begin;
        int start2 = mid+1;
        int satrtCopy = 0;
        while(start1<=mid && start2<=end){
            if(array[start1]<array[start2]){
                copy[satrtCopy++] = array[start1++];
            }else{
                copy[satrtCopy++] = array[start2++];
            }
        }
        while (start1<=mid){
            copy[satrtCopy++] = array[start1++];
        }
        while (start2<=end){
            copy[satrtCopy++] = array[start2++];
        }
        satrtCopy = 0;
        for(int i=begin;i<=end;i++){
            array[i] = copy[satrtCopy++];
        }
    }

    public static void main(String[] args) {
        int[] array = {5,4,6,8,1,3,5,1,56456,5,2};
        new MergeSort().mergeSort(array,0,array.length-1);
        for(int a:array){
            System.out.print(a+" ");
        }
    }
}

冒泡排序

package sort;

public class BubbleSort {
    public void bubble(int[] array){
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array.length-i-1;j++){
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                }
            }
        }
    }
    public void swap(int[] array,int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] array = {5,4,6,8,1,3};
        new BubbleSort().bubble(array);
        for(int a:array){
            System.out.print(a+" ");
        }
    }
}

Search

    Table of Contents