插入排序、选择排序、归并排序、堆排序、快速排序的JAVA实现

静下心来，重拾初衷

那么就从最基本的开始吧

package com.thedman.test;


public class Test {

public static void main(String[] args) {
int[] input = new int[]{24, 55, 12, 0, 78, 15, 99, 88, 100, 25};

//insertionSort(input);
//selectionSort(input);
//mergeSort(input);
//heapSort(input);
quickSort(input, 0, input.length - 1);

for (int i : input) {
System.out.print(i + ", ");
}
}

/**
 * 交换数组中俩数据位置
 * @param data
 * @param i
 * @param j
 */
private static void swap(int[] data, int i, int j) {
if (i == j) {
return;
}
data[i] = data[i] + data[j];
data[j] = data[i] - data[j];
data[i] = data[i] - data[j];
}

/**
 * 插入排序
 * 最坏复杂度为O(n^2)
 * @param input
 */
public static void insertionSort(int[] input) {
int length = input.length;
for (int i = 0; i < length; i++) {
int j = i;
while (j > 0 && input[j] < input[j - 1]) {
swap(input, j, j-1);
j -- ;
}
}
}

/**
 * 选择排序
 * 最坏复杂度为O(n^2)
 * @param input
 */
public static void selectionSort(int[] input) {
        for (int i = 0; i < input.length; i++) {  
            int min = i;
            for (int j = i + 1; j < input.length; j++) {  
                if (input[min] > input[j]) {
                    min = j;
                }  
            }  
            if (i != min) {
                swap(input, min, i);
            }  
        }  
}

/**
 * 归并排序
 * 最坏复杂度为O(nlogn)
 * @param input
 */
public static void mergeSort(int[] input) {
sort(input, 0, input.length - 1);
}

private static void sort(int[] data, int left, int right) {
if (left >= right)
return;

int center = (left + right) / 2;
sort(data, left, center);
sort(data, center + 1, right);
merge(data, left, center, right);

}

private static void merge(int[] data, int left, int center, int right) {
        // 临时数组  
        int[] tmpArr = new int[data.length];  
        // 右数组第一个元素索引  
        int mid = center + 1;  
        // third 记录临时数组的索引  
        int third = left;  
        // 缓存左数组第一个元素的索引  
        int tmp = left;  
        while (left <= center && mid <= right) {  
            // 从两个数组中取出最小的放入临时数组  
            if (data[left] <= data[mid]) {  
                tmpArr[third++] = data[left++];  
            } else {  
                tmpArr[third++] = data[mid++];  
            }  
        }  
        // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）  
        while (mid <= right) {  
            tmpArr[third++] = data[mid++];  
        }  
        while (left <= center) {  
            tmpArr[third++] = data[left++];  
        }  
        // 将临时数组中的内容拷贝回原数组中  
        // （原left-right范围的内容被复制回原数组）  
        while (tmp <= right) {  
            data[tmp] = tmpArr[tmp++];  
        }  
}

/**
 * 堆排序
 * 复杂度O(nlogn)
 * @param input
 */
public static void heapSort(int[] input) {
for (int i = 0; i < input.length; i++) {  
            createMaxdHeap(input, input.length - 1 - i);  
            swap(input, 0, input.length - 1 - i);  
        } 
}

private static void createMaxdHeap(int[] data, int lastIndex) {  
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {  
            // 保存当前正在判断的节点  
            int k = i;  
            // 若当前节点的子节点存在  
            while (2 * k + 1 <= lastIndex) {  
                // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点  
                int biggerIndex = 2 * k + 1;  
                if (biggerIndex < lastIndex) {  
                    // 若右子节点存在，否则此时biggerIndex应该等于 lastIndex  
                    if (data[biggerIndex] < data[biggerIndex + 1]) {  
                        // 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值  
                        biggerIndex++;  
                    }  
                }  
                if (data[k] < data[biggerIndex]) {  
                    // 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k  
                    swap(data, k, biggerIndex);  
                    k = biggerIndex;  
                } else {  
                    break;  
                }  
            }  
        }  
    } 

/**
 * 快速排序
 * 复杂度O(n^2)
 * @param input
 * @param start
 * @param end
 */
public static void quickSort(int[] input, int start, int end) {  
        if (start >= end)  
            return;  
        //以起始索引为分界点  
        int pivot = input[start];  
        int i = start + 1;  
        int j = end;  
        while (true) {  
            while (i <= end && input[i] < pivot) {  
                i++;  
            }  
            while (j > start && input[j] > pivot) {  
                j--;  
            }  
            if (i < j) {  
                swap(input, i, j);  
            } else {  
                break;  
            }  
        }  
        //交换 j和分界点的值  
        swap(input, start, j);  
        //递归左子序列  
        quickSort(input, start, j - 1);  
        //递归右子序列  
        quickSort(input, j + 1, end);  
    }  

}

以上，堆排序的原理还是不太懂，归并、堆、快速排序的实现如果让自己笔试的时候写，可能还写不出