排序算法

排序算法是比较基础，且比较重要的数据结构内容。今天在这里简单总结一下基本原理、代码和注意事项，让自己有一个比较全面的了解，也能方便查看。
本文一共讲了选择排序、冒泡排序、快速排序、归并排序、插入排序、希尔排序、堆排序、桶排序、基数排序九种排序算法。

选择排序

循环中每次选择要排序记录中最小的一个和最前面的交换。换上n趟，就排好啦~

• 时间复杂度：O(n^2)

    public int[] selectSort(int[] input) {

        for (int i = 0; i < input.length; i++) {
            int min = input[i];
            int index = i;
            for (int j = i + 1; j < input.length; j++) {
                if (input[j] < min) {
                    min = input[j];
                    index = j;
                }
            }
            int temp = input[i];
            input[i] = input[index];
            input[index] = temp;
        }
        return input;
    }

冒泡排序

一趟排序中依次比较相邻的两个，如果前面的大于后面的就交换，这样一趟下来最大的一定会到最后一位。然后运行n趟，这整个为n的记录就排好序了。

• 时间复杂度： O(n^2)

    public int[] bubbleSort(int[] input) {
        for (int i = 0; i < input.length; i++) {
            for (int j = 0; j < input.length - 1 - i; j++) {
                if (input[j] > input[j + 1]) {
                    int temp = input[j];
                    input[j] = input[j + 1];
                    input[j + 1] = temp;
                }
            }
        }
        return input;
    }

快速排序

每一次排序都会把待排序的记录分成两部分，其中一部分均比另一部分小，然后再对这两两部分分别排序，直到完全有序。

• 具体做法：选择记录中第一个数字作为关键字，将传入的左边界和右边界作为左右指针，先循环减少右指针寻找右边小于关键字的挪到左指针的位置，然后再循环增加左指针从左边找大于关键字的挪到右指针位置，直到左指针等于右指针，然后将关键字赋到这个位置。然后再递归调用这两部分。直到结束。
• 时间复杂度：O(nlogn)
• 注意：排序算法被认为是相同时间复杂度里平均性能最好的。如果序列基本有序会退化为冒泡排序，时间复杂度为O（n^2）。

    public int[] quickSort(int[] input, int low, int height) {
        if (low >= height) {
            return null;
        }

        int left = low;
        int right = height;
        int key = input[left];
        while (left < right) {
            while (left < right && input[right] >= key) {
                right--;
            }
            input[left] = input[right];
            while (left < right && input[left] <= key) {
                left++;
            }
            input[right] = input[left];
        }
        input[left] = key;

        quickSort(input, low, left - 1);
        quickSort(input, right + 1, height);

        return input;
    }

归并排序

采用递归的方法，将待排序的记录分成几个有序的小部分，然后再进行合并。

• 具体做法：递归的将记录分为最小部分，然后再从合并中排序。合并的过程中，先从两个的左边开始比较，如果较小就放到临时数组里，直到有一方空了，再把另一个数组的剩余部分全部放进临时数组里。然后再把临时数组重新放到原数组。最后合并为一个完全有序的记录。
• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

    public void mergeSort(int[] input, int low, int height) {
        if (low < height) {
            int mid = (low + height) / 2;
            mergeSort(input, low, mid);
            mergeSort(input, mid + 1, height);
            merge(input, low, height);
        }
    }

    public void merge(int[] input, int left, int right) {
        int[] temp = new int[input.length];
        int mid = (left + right) / 2;
        int index = left;

        int i = left;
        int j = mid + 1;
        while (i <= mid && j <= right) {
            if (input[i] < input[j]) {
                temp[index++] = input[i++];
            } else {
                temp[index++] = input[j++];
            }
        }

        while (i <= mid) {
            temp[index++] = input[i++];
        }
        while (j <= right) {
            temp[index++] = input[j++];
        }

        for (int a = left; a <= right; a++) {
            input[a] = temp[a];
        }
    }

直接插入排序

将一个记录插入到已经排好序的有序表中，得到一个新的、记录数增一的有序表。

• 形象描述：就像打牌的时候，我们每抓一张牌都会把这张牌插入到已经排好顺序的牌里面。
• 具体做法：外层循环从1到n-1。内层循环查看当前数字是否比前一个数字小，如果大的话就跳过，如果小就要循环已排好序数列，然后将当前数字插入到合适位置。
• 时间复杂度：O(n^2)
• 注意：在基本有序情况下，直接插入算法是最快的排序算法，时间复杂度为O（n）

    public int[] straightInsertionSort(int[] input) {
        for (int i = 1; i < input.length; i++) {
            int temp = input[i];
            int j;
            for (j = i - 1; j >= 0 && temp < input[j]; j--) {
                input[j + 1] = input[j];
            }
            input[j + 1] = temp;
        }
        return input;
    }

希尔排序

先将整个待排序记录分为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再进行一次直接插入排序。

• 具体实现：先选择插入的距离为length/2完成第一次插入排序，然后再从原来的基础上/2,最后当距离变成1的时候就变成了直接插入排序。
• 时间复杂度：不好说，但肯定比直接插入排序智能点。

    public int[] shellSort(int[] input) {
        int dk = input.length / 2;
        while (dk > 0) {
            for (int i = dk; i < input.length; i++) {
                int temp = input[i];
                int j;
                for (j = i - dk; j >= 0 && temp < input[j]; j -= dk) {
                    input[j + dk] = input[j];
                }
                input[j + dk] = temp;
            }
            dk /= 2;

        }
        return input;
    }

堆排序

先将记录转化为最大堆或者最小堆，然后不断地将第一个数字拿出来存储，然后调整堆，最后堆为空的时候，排序完成。

• 具体视线：首先生成堆，然后把堆的第一个元素和最后一个元素交换，减少堆的长度。然后重新把被破坏了的堆重新调整成堆。然后再完成交换，直到结束。
• 时间复杂度：O(nlogn)

    public int[] heapSort(int[] input) {
        buildHeap(input);

        for (int i = input.length - 1; i >= 0; i--) {
            int t = input[i];
            input[i] = input[0];
            input[0] = t;

            adjustHeap(input, 0, i);
        }
        return input;
    }

    private void buildHeap(int[] input) {
        for (int i = (input.length - 1) / 2; i >= 0; i--) {
            adjustHeap(input, i, input.length);
        }
    }

    private void adjustHeap(int[] input, int s, int length) {
        int temp = input[s];
        int child = 2 * s + 1;
        while (child < length) {
            if (child + 1 < length && input[child + 1] > input[child]) {
                child++;
            }
            if (input[child] > input[s]) {
                input[s] = input[child];
                input[child] = temp;
                s = child;
                child = 2 * s + 1;
            } else {
                break;
            }
        }
    }

桶排序

新建一个容量为最大数字+1个的数组空间。然后把每个数直接放到该数组与自己对应的地方，然后按次序拿出来就好了。

• 时间复杂度：O(n)
• 注意：考虑负数和有相同数字的情况，本程序没考虑。

    public int[] bucketSort(int[] input, int max) {
        int[] temp = new int[max + 1];
        for (int i = 0; i < input.length; i++) {
            temp[input[i]] = input[i];
        }
        int index = 0;
        for (int i = 0; i < max + 1; i++) {
            if (temp[i] != 0) {
                input[index++] = temp[i];
            }
        }
        return input;
    }

基数排序

分别以各位数字进行桶排序，然后按顺序取出，遍历完所有位遍完成排序。

• 具体实现：先建立一个二维数组，然后将个位上相同的数字放进同一个桶，然后依次取出放回原数组，这样就实现了个位上的有序，然后百位，千位，最后遍历完成所有位即完成排序。
• 时间复杂度：O(d(n+rd))
• 空间复杂度：O(rd)
• 注意：要考虑存在负数的情况。本程序里没有考虑。

    public int[] radixSort(int[] input, int max) {
        int[][] temp = new int[10][input.length];
        int[] num = new int[10];

        int index = 1;
        int n = 1;
        while (index <= max) {
            for (int i = 0; i < input.length; i++) {
                int wei = input[i] / n % 10;
                temp[wei][num[wei]++] = input[i];
            }
            int count = 0;
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < input.length; j++) {
                    if (temp[i][j] == 0) {
                        break;
                    } else {
                        input[count++] = temp[i][j];
                    }
                }
            }
            for (int i = 0; i < 10; i++) {
                num[i] = 0;
                for (int j = 0; j < input.length; j++) {
                    temp[i][j] = 0;
                }
            }

            index++;
            n *= 10;
        }
        return input;
    }

就酱~

欢迎关注【Funny新青年】微信公众号～