最全的数据结构排序算法实现及比较

冒泡排序

类似暴力破解，1 – n 个，每个都比较一次。完成排序

public void sort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len - 1; j++) {
            if (arr[i] > arr[j]) {
                SwapUtil.swap(arr, i, j);
            }
        }
    }
}

选择排序

[ 排序完毕 | 未排序] 每次从未排序的找一个最小的放入到排序完毕的后边

public void sort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        int index = findMinIndex(arr, i);
        if (index !=  -1) {
            SwapUtil.swap(arr, i, index);
        }
    }
}
 
public int findMinIndex(int[] arr, int begin) {
    int len = arr.length;
    int index = -1, elem = arr[begin];
    for (; begin < len; begin++) {
        if (arr[begin] < elem) {
            index = begin;
            elem = arr[begin];
        }
    }
    return index;
}
堆排序

堆排序

先进行堆的构建，再进行堆的调整

@Override
public void sort(int[] arr) {
    int len = arr.length;
    sort(arr, len);
}
 
private void sort(int[] arr, int len) {
    buildMaxHeap(arr, len);
    adjust(arr, len);
}
 
private void adjust(int[] arr, int len) {
    for (int i = len - 1; i > 0; i--) {
        SwapUtil.swap(arr, 0, i);
        adjustHeap(arr, 0, i);
    }
}
 
private void buildMaxHeap(int[] arr, int len) {
    // 这里索引从 0 开始，所以最后一个非叶子子节点 array.length / 2 - 1;
    for (int i = len / BUILD_HEAP_SEPARATED - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    System.out.println("build heap : " + Arrays.toString(arr));
}
 
private void adjustHeap(int[] arr, int i, int length) {
    // 先把当前元素取出来，因为当前元素可能要一直移动
    int temp = arr[i];
    // 从左孩子开始遍历 （ 2i + 1）
    for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
        // 若右孩子存在，且右孩子大于左孩子
        if (k + 1 < length && arr[k] < arr[k + 1]) {
            // 转移到右孩子
            k++;
        }
        // 如果发现结点(左右子结点)大于根结点，则进行值的交换
        if (arr[k] > temp) {
            SwapUtil.swap(arr, i, k);
            // 如果子节点更换了，则以子节点为根的子树会受到影响,
     // 所以，循环对子节点所在的树继续进行判断
            i  =  k;
        } else {
            //不用交换，直接终止循环
            break;
        }
    }
}

希尔排序

这里采用数组长度一半作为希尔增量进行排序，每次减少一半，知道增量为1.排序完毕。

 @Override
public void sort(int[] arr) {
    int step = arr.length / 2;
    for ( ; step > 0; step /= 2) {
        for (int i = step; i < arr.length; i++) {
            int value = arr[i];
            int j;
            // 跳跃的插入, 因为增量的存在，所以，后移时，是当前增量后移
            for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
                arr[j + step] = arr[j];
            }
            arr[j + step] = value;
        }
    }
 
}

插入排序

类似于选择排序，分为【排序 | 未排序区域】每次从未排序区域选取一个，再排序区域寻找位置，然后后移交换。

@Override
public void sort(int[] arr) {
    int len = arr.length;
    for (int i = 1; i < len; i++) {
        int elem = arr[i];
        int index = getIndex(arr, i, elem);
        if (index != i) {
            retreat(arr, index, i);
            arr[index] = elem;
        }
    }
}
 
/**
 * 获取插入排序所在索引
 * @param arr 数组
 * @param limit 已排序区间上界
 * @param elem 待排序元素
 * @return 要插入的数组
 */
private int getIndex(int[] arr, int limit, int elem) {
    for (int i = 0; i < limit; i++) {
        if (elem < arr[i]) {
            return i;
        }
    }
    return limit;
}
 
/**
 * 将数组内一段元素后移
 * @param arr 数组
 * @param begin 区间下界
 * @param end 区间上界
 */
private void retreat(int[] arr, int begin, int end) {
    while(end > begin) {
        arr[end] = arr[end - 1];
        end--;
    }
}

二路归并排序

@Override
public void sort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1);
}
 
public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
 
public void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[arr.length];
    int leftIndex = left, rightIndex = mid + 1, tempIndex = left;
    while (leftIndex <= mid && rightIndex <= right) {
        if (arr[leftIndex] < arr[rightIndex]) {
            temp[tempIndex++] = arr[leftIndex++];
        } else {
            temp[tempIndex++] = arr[rightIndex++];
        }
    }
    while (leftIndex <= mid) {
        temp[tempIndex++] = arr[leftIndex++];
    }
    while(rightIndex <= right) {
        temp[tempIndex++] = arr[rightIndex++];
    }
    // 将归并结果归坏到原数组中
    while (left <= right) {
        arr[left] = temp[left++];
    }
}

快速排序

设数组第一个元素为基准,

第一步：数组中所有元素，小于 基准 放到左边，大于 基准 放到右边，此时数组分为两部分，对于基准来说已经处于它应处的位置

第二步，对左右两半数组继续执行第一步，递归完毕，数组有序

时间复杂度: O(n*log2n) – 空间复杂度: good: O(log2n) – bad: O(n)

@Override
public void sort(int[] arr) {
    int len = arr.length;
    sort(arr, 0, len - 1);
}
 
private void sort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = partition(arr, left, right);
        sort(arr, left, mid - 1);
        sort(arr, mid + 1, right);
    }
}
 
private int partition(int[] arr, int left, int right) {
    int sentry = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= sentry) {
            right--;
        }
        arr[left] = arr[right];
        while(left < right && arr[left] <= sentry) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = sentry;
    return left;
}

排序比较