基于Java语言的排序算法

image.png

各排序代码如下：

一：交换排序

// 冒泡排序
@Override
public void bubbleSort(int[] data) {
    if (null == data || data.length <= 1) {
        return;
    }
    final int length = data.length;
    int temp = 0;
    // 外层循环控制比较趟数 (每比较一趟，会确定一个数的最终位置, 会比较data.length - 1 趟)
    for (int i = 0; i < length - 1; i++) { // 注意下标  结尾是 length - 1
        // 内层循环是比较第[i]元素与，[i + 1, data.length]中所有元素的比较
        for (int j = 0; j < length - 1 - i; j++) {
            if (data[j + 1] < data[j]) {
                temp = data[j + 1];
                data[j + 1] = data[j];
                data[j] = temp;
            }
        }
    }
}

// 快速排序
@Override
public void quickSort(int[] data) {
    if (null == data || data.length <= 1) {
        return;
    }
    long startTime = System.currentTimeMillis();
    inner_quickSort(data, 0, data.length - 1);
    System.out.println("快速排序时间：" + (System.currentTimeMillis() - startTime));
}

private void inner_quickSort(int[] data, int start, int end) {
    if (start < end) {
        int i = partition(data, start, end);
        inner_quickSort(data, start, i - 1);
        inner_quickSort(data, i + 1, end);
    }
}

private int partition(int[] array, int start, int end) {
    int temp = array[start]; // 用子序的第一个作为基准
    int i = start, j = end;
    while (i < j) {
        // 先遍历右边的数据
        while (i < j && array[j] > temp) {
            j--;
        }
        if (i < j) {
            array[i] = array[j];
            i++;
        }

        // 再遍历左边的数据
        while (i < j && array[i] < temp) {
            i++;
        }
        if (i < j) {
            array[j] = array[i];
            j--;
        }
        // array[i] = temp;
    }
    array[i] = temp;
    return i;
}

二：选择排序

// 简单选择排序
@Override
public void simpleSelect(int[] data) {
    if (null == data || data.length <= 1) {
        return;
    }
    final int length = data.length;
    for (int i = 0; i < length; i++) {
        int target = i;
        for (int j = i + 1; j < length; j++) {
            if (data[j] < data[target]) {
                target = j;
            }
        }
        int temp = 0;
        if (target != i) {
            temp = data[target];
            data[target] = data[i];
            data[i] = temp;
        }
    }

}

// 堆排序
@Override
public void heapSort(int[] data) {
    // TODO Auto-generated method stub

}

三： 插入排序

// 直接插入排序
@Override
public void directInsertSort(int[] data) {
    for (int i = 1; i < data.length; i++) {
        inner(data, 1, i);
    }
}

// 希尔排序
@Override
public void shellSort(int[] data) {
    int length = data.length;
    for (int gap = length / 2; gap > 0; gap /= 2) {
        for(int j = gap; j < length; j++) {
            inner(data, gap, j);
        }
    }
}

private void inner(int[] data, int gap, int i) {
    int willInsert = data[i];
    int j;
    for (j = i; j >= gap && data[j - gap] > willInsert; j -= gap) {
        data[j] = data[j - gap];
    }
    data[j] = willInsert;
}

四： 归并排序

时间复杂度：O(nlogn)
空间复杂度：O(N) ，归并排序需要一个与原数组相同长度的数组来做辅助排序。
稳定性：是稳定的排序算法

@Override
public void mergeSort(int[] data) {
    if (null == data || 1 >= data.length) {
        return;
    }
    sort(data, 0, data.length - 1);
}

private void sort(int[] a, int start, int end) {
    if (start < end) {// 当子序列中只有一个元素时结束递归
        final int mid = (start + end) / 2;// 划分子序列
        // 对左侧子序列进行递归排序
        sort(a, start, mid);
        // 对右侧子序列进行递归排序
        sort(a, mid + 1, end);
        // 合并
        merge(a, start, mid, end);
    }
}

// 两路归并算法，两个排好序的子序列合并为一个子序列
private void merge(int[] a, int left, int mid, int right) {
    int[] tmp = new int[a.length];// 辅助数组
    int p1 = left, p2 = mid + 1, tmpIndex = left;// p1、p2是检测指针，k是存放指针
    
    // 比较左右两部分的元素，哪个小就把哪个元素填入tmp中
    while (p1 <= mid && p2 <= right) {
        tmp[tmpIndex++] = a[p1] <= a[p2] ? a[p1++] : a[p2++];
    }

    // 如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
    // (以下两个while只有一个会执行)
    while (p1 <= mid)
        tmp[tmpIndex++] = a[p1++];

    while (p2 <= right)
        tmp[tmpIndex++] = a[p2++];

    // 把最终的排序的结果复制给原数组
    for (int i = left; i <= right; i++)
        a[i] = tmp[i];
}