九大基本排序算法

发表于 | 更新于 | 分类于 | 评论数：

冒泡排序

冒泡排序的平均复杂度是O(N^2),最好的情况O(N),最坏的情况O(N^2);空间复杂度O(1)；稳定算法

/**
 * A为数组，n为数组的长度
 */
private static int[] bubbleSort(int[] A, int n) {
    int temp;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (A[j] > A[j + 1]) {
                temp = A[j + 1];
                A[j + 1] = A[j];
                A[j] = temp;
            }
        }
    }
    return A;
}

选择排序

选择排序时间复杂度 O(N^2)，最坏的情况O(N^2);空间复杂度O(1)；不稳定算法

/**
 * A为数组，n为数组的长度
 */
private static int[] selectionSort(int[] A, int n) {
    int minPos = 0;
    int temp;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[minPos]) {
                minPos = j;
            }
        }
        temp = A[minPos];
        A[minPos] = A[i];
        A[i] = temp;
        minPos = i + 1;
    }
    return A;
}

插入排序

插入排序的平均复杂度是O(N^2)，最好的情况O(N)，最坏的情况O(N^2);空间复杂度O(1)；稳定算法

/**
 * A为数组，n为数组的长度
 */
private static int[] insertionSort(int[] A, int n) {
    int temp;
    for (int i = 2; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (A[i] < A[j]) {
                temp = A[j];
                A[j] = A[i];
                A[i] = temp;
            }
        }
    }
    return A;
}

归并排序

归并排序时间复杂度O(N*logN),最好的情况O(N*logN)，最坏的情况O(N*logN)；空间复杂度O(N)；稳定算法

/**
 * A为数组，n为数组的长度
 */
private static int[] mergeSort(int[] A, int n) {
    if (n > 1) {
        int k = n / 2;
        int[] temp1 = new int[k];
        int[] temp2 = new int[n - k];

        for (int i = 0; i < k; i++) {
            temp1[i] = A[i];
        }
        for (int i = k; i < n; i++) {
            temp2[i - k] = A[i];
        }
        temp1 = mergeSort(temp1, k);
        temp2 = mergeSort(temp2, n - k);

        int i = 0;
        int j = 0;
        int x = 0;
        int[] temp = new int[n];

        while (i < k && j < n - k) {
            if (temp1[i] <= temp2[j]) {
                temp[x] = temp1[i];
                x++;
                i++;
            } else {
                temp[x] = temp2[j];
                x++;
                j++;
            }
        }

        while (i < k) {
            temp[x] = temp1[i];
            x++;
            i++;
        }

        while (j < n - k) {
            temp[x] = temp2[j];
            x++;
            j++;
        }
        return temp;
    }
    return A;
}

快速排序

快速排序的平均复杂度是O(N*logN)，最好的情况O(N*logN)，最坏的情况O(N^2);空间复杂度O(logN)；不稳定算法

/**
 * A为数组，n为数组的长度
 */
private static int[] quickSort(int[] A, int n) {
    qSort(A, 0, n - 1);
    return A;
}

/**
 * 
 * @param A
 *            数组
 * @param start
 *            数组起始位
 * @param end
 *            数组终止位
 */
public static void qSort(int[] A, int start, int end) {
    if (start < end) {
        Random random = new Random();
        // 产生一个随机数
        int nextInt = random.nextInt(end - start + 1) + start;
        // 把随机位和数组最后一位交换
        int temp = A[end];
        A[end] = A[nextInt];
        A[nextInt] = temp;
        // 比A[nextInt]小的数的个数
        int lt = 0;

        for (int i = start; i < end; i++) {
            if (A[i] <= A[end]) {
                int temp1 = A[lt + start];
                A[lt + start] = A[i];
                A[i] = temp1;
                lt++;
            }
        }
        // 把数组最后一位和A[start + lt]交换
        int temp2 = A[start + lt];
        A[lt + start] = A[end];
        A[end] = temp2;
        // 递归
        qSort(A, start, lt + start - 1);
        qSort(A, lt + start + 1, end);
    }
}

堆排序

时间复杂度 O(N*logN),最坏O(N*logN);不稳定算法

/**
 * 从堆顶中取值，再重新建堆
 * 
 * @param A
 *            数组
 * @param n
 *            数组长度
 * @return
 */
private static int[] heapSort(int[] A, int n) {
    while (n > 0) {
        sift(A, n);
        int temp = A[n - 1];
        A[n - 1] = A[0];
        A[0] = temp;
        n--;
        sift(A, n);
    }
    return A;
}

/**
 * 建堆
 * 
 * @param A
 * @param n
 */
public static void sift(int[] A, int n) {
    // 最后一个非终端节点
    int temp = n / 2;

    while (temp > 0) {
        int tt = 2 * temp - 1;
        if (2 * temp <= n - 1) {
            if (A[2 * temp] < A[2 * temp - 1]) {
                tt = 2 * temp - 1;
            } else {
                tt = 2 * temp;
            }
        }
        // 如果子节点大于父节点
        if (A[temp - 1] < A[tt]) {
            int t = A[temp - 1];
            A[temp - 1] = A[tt];
            A[tt] = t;
        }

        // 保证下面的堆为大顶堆
        for (int i = (tt + 1); i <= n; i = 2 * i) {
            int k = 2 * i - 1;
            if (k < n) {
                if (i * 2 + 1 <= n) {
                    if (A[2 * i] > A[2 * i - 1]) {
                        k = 2 * i;
                    }
                }
                if (A[i - 1] < A[k]) {
                    int t = A[i - 1];
                    A[i - 1] = A[k];
                    A[k] = t;
                }
            }
        }
        // 节点自减
        temp--;
    }
}

希尔排序

希尔排序的平均复杂度是O(N*logN)~O(N^2)，最好的情况O(N^1.3)，最坏的情况O(N^2)；空间复杂度O(1);不稳定算法

/**
 * A为数组，n为数组的长度
 */
private static int[] shellSort(int[] A, int n) {
    Random random = new Random();
    // 步长
    int step = random.nextInt(n);
    sSort(A,step);
    return A;
}

/**
 * 
 * @param A
 * @param start
 *            数组起始位
 * @param end
 *            数组终止位
 */
public static void sSort(int[] A, int step) {
    // 当步长大于0时循环
    while (step > 0) {
        for (int i = step; i < A.length; i++) {
            int k = i;
            int temp = k - step;
            while (temp >= 0) {
                if (A[k] < A[temp]) {
                    int temp2 = A[k];
                    A[k] = A[temp];
                    A[temp] = temp2;
                    k = temp;
                }
                temp -= step;
            }
        }
        // 步长自减
        step--;
    }
}

计数排序

时间复杂度 O(N)；

/**
 * 
 * @param A
 *            数组
 * @param n
 *            数组长度
 * @return
 */
private static int[] countingSort(int[] A, int n) {
    int temp = A[0];
    for (int i = 1;i<n ;i++) {
        if(A[i]>temp){
            temp = A[i];
        }
    }

    int[] count = new int[temp+1];

    for (int i = 0; i < n; i++) {
        count[A[i]]++;
    }
    int[] result = new int[n];
    int length = 0;
    for (int i = 0; i < count.length; i++) {
        while(count[i]>0){
            result[length] = i;
            count[i]--;
            length++;
        }
    }
    return result;
}

基数排序

时间复杂度 O (nlog(r)m)，其中r为所采取的基数，而m为堆数;空间复杂度O(N)；稳定算法

public static int[] radixSort(int[] A, int n) {

    int index = 0;
    for (int i = 1; i < n; i++) {
        if (A[i] > A[index]) {
            index = i;
        }
    }

    int temp = A[index];
    int count = 0;
    while (temp / 10 > 0) {
        count++;
        temp /= 10;
    }
    count++;

    int[][] bucket = new int[10][n + 1];

    int temp1 = count;
    while (count > 0) {

        for (int i = 0; i < bucket.length; i++) {
            bucket[i][0] = 0;
        }

        for (int i = 0; i < n; i++) {
            int num;
            if (temp1 - count == 0) {
                num = A[i] % 10;
            } else {
                int tt = (int) Math.pow(10, temp1 - count);
                num = (int) A[i] / tt % 10;
            }
            int length = bucket[num][0];
            bucket[num][length + 1] = A[i];
            length++;
            bucket[num][0] = length;
        }
        int length = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < bucket[i][0]; j++) {
                A[length] = bucket[i][j + 1];
                length++;
            }
        }
        count--;
    }
    return A;
}
俞其荣 wechat
欢迎订阅我的微信公众号来获取我的动态！
坚持原创技术分享，您的支持将鼓励我继续创作！