排序实现

algorithm

排序算法实现

package com.sort;
public class SortLearn {
    public static void main(String[] args) {
        int [] A = new int[] {1,3,2,10,5,4,-1,6};
//      int [] A = new int[] {1,2,-1,6};
//      insert_sort(A);
//      select_sort(A);
//      bubble_sort(A);
//      merge_sort(A,0,A.length-1);
        quick_sort(A,0,A.length-1);
        print(A);
    }
    // 快速排序
    // 划分：
    // 递归排序
    public static void quick_sort(int []A,int l,int r) {
        if(l >= r)// 递归出口，只有一个元素的数组一定是有序的
            return ;
        int k = partition(A,l,r); // 划分数组，A[k] 左边比A[k]小，右边不大于A[k]
        quick_sort(A,l,k-1); // 分别对两边进行排序
        quick_sort(A,k+1,r); 
    }
    // 快排，分割数组
    private static int partition(int[] A, int l, int r) {
        int p = A[l];
        int i =l,j = r;
        while(i < j) {
            while(i < j && A[j] >= p ) // 从右边查找一个比p小的元素，放置到p的前面
                j--;
            if(i < j)
                A[i] = A[j];
            while(i < j && A[i] < p)  // 左边查找一个比p大的元素，放到p的后面
                i++;
            if(i < j)
                A[j] = A[i];
        }
        A[i] = p;// 放置p，这个时候A[l,i) 小于p,A[i,r]不小于p,数组从p这个位置看，左右两边大致是两类数据了
        return i; // p的位置
    }
    // 归并排序
    // 划分：直到最小的单位一个元素的数组时
    // 合并：合并有序数组
    public static void merge_sort(int[] A,int l,int r) {
        if(l >= r) // 递归的出口，只有一个元素时，不需要在递归了
            return; 
        int k = (l + r ) / 2; // 把数据一分为2
        merge_sort(A, l, k); // A[l,k] 进行递归排序
        merge_sort(A, k+1, r); // A[k+1,r] 递归排序
        // 下面是合并两个排序数组的过程，可以参见merge函数
        int [] B = new int[r - l + 1];// 新建立一个数组 
        int c = 0;
        int i = l, j = k + 1;
        while(i <= k && j <= r) { // 合并两个数组，选择较小的那个放置B中
            if(A[i] < A[j]) {
                B[c++] = A[i++];
            }else {
                B[c++] = A[j++];
            }
        }
        // 可能A[i] 数据还有
        while(i <= k) {
            B[c++] = A[i++];
        }
        // 可能A[j] 数据还有
        while(j <= r) {
            B[c++] = A[j++];
        }
        // 把B中数据复制到A中[l,r]
        c = 0;
        while(l <= r) {
            A[l++] = B[c++];
        }
    }
    // 归并合并两个有序数组
    public static void merge(int []A,int l,int k,int r) {
        int [] B = new int[r-l+1];
        int c = 0;
        int i = l,j = k+1;
        while(i <= k && j <= r) {
            if(A[i] < A[j]) {
                B[c++] = A[i++];
            }else {
                B[c++] = A[j++];
            }
        }
        while(i <= k) {
            B[c++] = A[i++];
        }
        while(j <= r) {
            B[c++] = A[j++];
        }
        c = 0;
        while(l <= r) {
            A[l++] = B[c++];
        }
    }
    public static void print(int[] A) {
//      System.out.println(A);
        for(int x:A) {
            System.out.printf("%d ",x);
        }
        System.out.println();
    }
    /// 冒泡排序
    public static void bubble_sort(int [] A) {
        int n = A.length;
        for(int i =0;i < n;i++) {// 排序趟数，因每次会冒出最大的一个数到最终排序好的位置上
            for(int j = 0;j < n-i-1;j++) { // 第i趟排序时，(n-i-1,n)的位置上已经是排序好的数据了
                if(A[j] > A[j+1]) {// 如果前面的比后面的大，则交换两个数，让大的数据往后冒
                    int t = A[j];
                    A[j] = A[j+1];
                    A[j+1] = t;
                }
            }
        }
        print(A);
    }
    //  插入排序
    public static void insert_sort(int [] A) {
        int n = A.length;
        for (int i =0 ;i < n;i++) {// 对A[i] 执行插入排序,i = 0 其实可以不用参加排序，因为就它自己一个元素，已经是有序的了
            int key = A[i];// 保存要排的数据
            int j;
            for( j = i-1; j >= 0; j--) { // 从[i-1,0] 查找一个A[i]能够正确放置的位置
                if(A[j] > key) { // 
                    A[j+1] = A[j]; // 前面的一个元素往后移动一位，腾出空间
                }else {
                    break;
                }
            }
            A[j+1] = key; // 把A[i] 放置到查找到的位置上
        }
        print(A);
    }
//  选择排序
    public static void select_sort(int[] A) {
        int n = A.length;
        for(int i = 0; i < n; i++) { // 选择排序的排序趟数
            int min = A[i]; // 假设A[i] 是最小的元素，从[i,n) 查找最小的元素
            int min_index = i; // 记录最小元素的索引
            for(int j = i + 1; j < n; j++) { // 已经假设A[i]最小，那么可以从[i+1,n) 查找最小的元素
                if(A[j] < min) { // 记录最小元素的位置和值
                    min = A[j];
                    min_index = j;
                }
            }
            if(min_index != i) { // 如果A[i] 不是最小元素，那么交换两个数
                int t = A[i];
                A[i] = A[min_index];
                A[min_index] = t;
            }
        }
        print(A);
    }
}