冒泡排序

什么是冒泡排序

• 先通過元素進(jìn)行比較找出最大數(shù)，如果是升序就放在最后，降序就放在首位，
• 每次遍歷都確定一個(gè)數(shù)的位置

算法思路

1. 從后往前比較相鄰的元素，如果后一個(gè)比前一個(gè)小，就互換位置
2. 針對(duì)所有的元素重復(fù)以上的步驟。

算法模型

  public void sort(int[] nums) {
        for(int i=0;i< nums.length;i++){
            boolean flag = true;
            for(int j= nums.length-1;j>i;j--){
                if(num[j]<nums[j-1]){
                    int temp = nums[j-1];
                    nums[j-1] = nums[j];
                    nums[j] = temp;
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }
    }

插入排序

什么是插入排序

對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

算法思路

1. 將第一個(gè)元素看做一個(gè)有序序列，把其他元素當(dāng)成是未排序序列
2. 從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置

算法模型

    public void 插入Sort() {
        int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
        int j = 0;
        for(int i=0;i<num.length;i++){
            int temp = num[I];
            // 將小于當(dāng)前位置的數(shù)后移
            for(j=i;j>0&&temp>num[j-1];j--){
                num[j] = num[j-1];
            }
            num[j] = temp;
        }
        System.out.println(Arrays.toString(num));
    }

選擇排序

算法思路

1. 在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置。
2. 從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾
3. 重復(fù)第二步，直到所有元素均排序完畢。

算法模型

    public void 選擇Sort(){
        int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
        for(int i=0;i<num.length-1;i++){
            int minIndex = i;
            for(int j=i;j<num.length;j++){
                if(num[j]<num[minIndex]){
                    minIndex = j;
                }
            }
            if(i!=minIndex){
                int temp = num[minIndex];
                num[minIndex] = num[i];
                num[i] = temp;
            }
        }
        System.out.println(Arrays.toString(num));
    }

快速排序

算法思路

1. 選基準(zhǔn)
2. 分區(qū)
3. 對(duì)分區(qū)迭代進(jìn)行1，2步驟

算法模型

    public void 快速Sort(){
        int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
        quickSort(num,0,num.length-1);
        System.out.println(Arrays.toString(num));
    }
    private void quickSort(int[] num,int left,int right){
        //遞歸結(jié)束條件左指針大于等于右指針
        if(left<right) {
            //分區(qū)
            int partitionIndex = partition(num, left, right);
            //遞歸左分區(qū)
            quickSort(num, left, partitionIndex-1);
            //遞歸右分區(qū)
            quickSort(num, partitionIndex+1, right);
        }

    }
    private int partition(int[] num,int left,int right){
        int pivot = left;
        int index = pivot+1;
        for(int i = index;i<=right;i++){
            if(num[i]<num[pivot]){
                swap(num,i,index);
                index++;
            }
        }
        swap(num,pivot,index-1);
        return index-1;
    }

歸并排序

算法思路

1. 遞歸將數(shù)組拆成左右兩個(gè)數(shù)組
2. 遞歸返回時(shí)，將左右兩個(gè)數(shù)組合并成有序數(shù)組

算法模版

public void 歸并Sort(){
        int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
        num = mergeSort(num);
        System.out.println(Arrays.toString(num));
    }

    private int[] mergeSort(int[] num){
        if(num.length<2){
            return num;
        }
        int[] left = Arrays.copyOfRange(num,0,num.length/2);
        int[] right = Arrays.copyOfRange(num,num.length/2,num.length);
        return merge(mergeSort(left),mergeSort(right));
    }

    private int[] merge(int[] left,int[] right){
        int i = 0;
        int j = 0;
        int[] result = new int[left.length+right.length];
        int cur;
        while(i<left.length||j<right.length){
            if(i==left.length){
                cur = right[j++];
            }else if(j==right.length){
                cur = left[i++];
            }else if(left[i]<=right[j]){
                cur = left[i++];
            }else{
                cur = right[j++];
            }
            result[i+j-1] = cur;
        }
        return result;
    }