插入排序

直接插入排序

public static void insertSort(int[] A) {
    int i, j, tmp;
    for(i = 1; i < A.length; i++) {
        if(A[i] < A[i-1]) {
            tmp = A[i];
            for(j = i - 1;  j >= 0 && tmp < A[j]; j--){
                A[j+1] = A[j];
            }
            A[j+1] = tmp;
        }
    }
}

折半插入排序

public static void halfInsertSort(int[] A) {
    int i, j, tmp, low, high, mid;
    for(i = 1; i < A.length; i++) {
        tmp = A[i];
        low = 0; high = i - 1;
        while(low <= high) {
            mid = (low + high) / 2;
            if (A[mid] > tmp) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        for (j = i - 1; j >= high + 1; j--) {
            A[j+1]  = A[j];
        }
        A[high+1] = tmp;
    }
}

交换排序

冒泡排序

public static void bubbleSort(int[] A) {
    int tmp;
    for(int i = 0; i < A.length - 1; i++) {
        for(int j = 0; j < A.length - 1 - i; j++) {
            if(A[j+1] < A[j]) {
                tmp = A[j];
                A[j] = A[j+1];
                A[j+1] = tmp;
            }
        }
    }
}

快速排序

/**
 * 快速排序
 */
public static void quickSort(int[] A) {
    quickSort(A, 0, A.length-1);
}

/**
 * 快速排序递归
 */
public static void quickSort(int A[], int low, int high) {
    if(low < high) {
        int pivotPos = partition(A, low, high);
        quickSort(A, low, pivotPos - 1);
        quickSort(A, pivotPos + 1, high);
    }
}

/**
 * 快速排序划分操作
 */
public static int partition(int A[], int low, int high) {
    int pivot = A[low];
    while(low < high) {
        while(low < high && A[high] >= pivot) {
            high--;
        }
        A[low] = A[high];
        while(low < high && A[low] <= pivot) {
            low++;
        }
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

选择排序

简单选择排序

public static void selectSort(int[] A) {
    int min, tmp;
    for(int i = 0; i < A.length - 1; i++) {
        min = i;
        for(int j = i + 1; j < A.length; j++) {
            if(A[j] < A[min]) {
                min = j;
            }
        }
        if(min != i) {
            tmp = A[i];
            A[i] = A[min];
            A[min] = tmp;
        }
    }
}

堆排序

/**
 * 堆排序
 */
public static void heapSort(int[] A) {
    int tmp;
    buildMaxHeap(A, A.length);
    for(int i = A.length - 1; i > 0; i--) {
        tmp = A[i];
        A[i] = A[0];
        A[0] = tmp;
        AdjustDown(A, 0, i);
        
    }
}

/**
 * 建立大根堆
 */
public static void buildMaxHeap(int A[], int len) {
    for(int i = len / 2; i >= 0; i--) {
        AdjustDown(A, i, len);
    }
}

/**
 * 向下调整
 */
public static void AdjustDown(int A[], int k, int len) {
    int tmp = A[k];
    for(int i = 2 * k; i < len; i *= 2) {
        if(i < len - 1 && A[i] < A[i+1]) {
            i++;
        }
        if(tmp >= A[i]) {
            break;
        } else {
            A[k] = A[i];
            k = i;
        }
    }
    A[k] = tmp;
}

其他排序

二路归并排序

/**
 * 二路归并排序
 */
public static void mergeSort(int[] A) {
    mergeSort(A, 0, A.length - 1);
}

/**
 * 二路归并排序核心
 */
public static void mergeSort(int A[], int low, int high) {
    if(low < high) {
        int mid = (low + high) / 2;
        mergeSort(A, low, mid);
        mergeSort(A, mid + 1, high);
        merge(A, low, mid, high);
        System.out.println(low + ", " + high);
    }
}

/**
 * 二路归并排序合并过程
 */
public static void merge(int A[], int low, int mid, int high) {
    int B[] = new int[A.length + 1];
    int i, j, k;
    for(k = low; k <= high; k++) {
        B[k] = A[k];
    }
    for(i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        if(B[i] <= B[j]) {
            A[k] = B[i++];
        } else {
            A[k] = B[j++];
        }
    }
    while(i <= mid) {
        A[k++] = B[i++];
    }
    while(j <= high) {
        A[k++] = B[j++];
    }
}