十分钟“手撕”七大排序

前言:可以通过目录来找你需要的排序的源代码。先是解释底层原理,后附带代码。 

目录

稳定的概念

一、插入排序

二、希尔排序

三、选择排序

四、堆排序

五、冒泡排序

六、快速排序

七、归并排序

八、排序总结 

额外:计数排序


稳定的概念

稳定性:

相同元素的相对位置排序完没有改变,则为稳定排序。 若排序后相同元素的相对位置发生变化,则为不稳定排序。

一、插入排序

原理如下:

从数据的第2位开始,跟前面的比,找到比该数据小的值插到后面,没有的话插到最前面。

 代码思路:

从第2位开始记为j,让j++把每一位都插到前面去。然后让j的前一位记为i,i--,让j从i开始往前插入。直到全插完。

插入排序特性总结:

    1. 元素集合越接近有序,直接插入排序算法的时间效率越高
    2. 时间复杂度:O(N^2)
    3. 空间复杂度:O(1),它是一种稳定的排序算法
    4. 稳定性:稳定
 

//插入排序
    /*
    1. 元素集合越接近有序,直接插入排序算法的时间效率越高
    2. 时间复杂度:O(N^2)
    3. 空间复杂度:O(1),它是一种稳定的排序算法
    4. 稳定性:稳定
    */
    public void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            //若j<0时,for循环进不来,所以再次放到0下标
            arr[j + 1] = tmp;
        }
    }

二、希尔排序

算法原理:

实际上就是插入排序的优化!插入排序一个一个插太慢了,这时希尔排序就出来了,把数据分多组,让他们先插入排序,然后缩短组数,再排序,循环,直到排完序。

代码思路:

我们先把一组数据总数/2分为gap组,先让gap组排序,然后gap/2,排序 ,循环往复,直到排完。如下图,若gap=2时,我们只需要arr[j]=arr[j+gap]和tmp就能交换插入了,gap=2有2轮,但是剩下一轮就只能再fori一次,若让i++就能交替循环,一次fori就能搞定了。

希尔排序特性:

  时间复杂度:O(N^1.25)到O(1.6 * N^1.25)(业内还没有准确的,只有个大概的)
  稳定性:不稳定

    //希尔排序
    /*
    *
    * 因为咋们的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的试验统计,我们暂时就按照:
    * O(N^1.25)到O(1.6 * N^1.25)来算。
      稳定性:不稳定
    * */
    public void shellSort(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            shell(gap, arr);
        }
    }

    private void shell(int gap, int[] arr) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + gap] = tmp;

        }
    }

三、选择排序

原理如下:

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元 素排完 。

 代码思路:

把第一个值作为tmp,然后i++往后循环,如果有小于tmp的就替换tmp,就找到最小的了,把它放到j(j=i+1)里面。for循环走完arr.length就排完序了。

插入排序特性总结:

1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用

2. 时间复杂度:O(N^2)

3. 空间复杂度:O(1)

4. 稳定性:不稳定

    //选择排序
    /*
    1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
    2. 时间复杂度:O(N^2)
    3. 空间复杂度:O(1)
    4. 稳定性:不稳定
    */
    public void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minindex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minindex]) {
                    minindex = j;
                }
            }
            swap(arr, minindex, i);

        }
    }

    private void swap(int[] arr, int minindex, int i) {
        int tmp = arr[minindex];
        arr[minindex] = arr[i];
        arr[i] = tmp;

    }

    //选择排序的优化(最大最小一起判断)
    public void selectSort2(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int minindex = left;
            int maxindex = left;

            for (int i = left + 1; i <= right; i++) {
                if (arr[i] < arr[minindex]) {
                    minindex = i;
                }
                if (arr[i] > arr[maxindex]) {
                    maxindex = i;
                }
            }
            swap(arr, minindex, left);
            swap(arr, maxindex, right);
            left++;
            right--;
        }
    }

四、堆排序

原理如下:

因为堆是有顺序的,不是大根堆就是小根堆。就是倒置一下顺序,逆序一下。我们只需要将最后一个排序跟堆首调换一下,然后向下调整,每个都如此,直到排完序。 

 代码思路:

比如大根堆,只需要将end=arr.length-1的元素和堆首元素交换,然后将堆首元素向下调整(找到两个根最大的那一个根,交换),然后end--。

插入排序特性总结:

    1. 堆排序使用堆来选数,效率就高了很多。
    2. 时间复杂度:O(N*logN)
    3. 空间复杂度:O(1)
    4. 稳定性:不稳定

    //堆排序
    /*
    1. 堆排序使用堆来选数,效率就高了很多。
    2. 时间复杂度:O(N*logN)
    3. 空间复杂度:O(1)
    4. 稳定性:不稳定
    */
    public void heapSort(int[] arr) {
        createBigHeap(arr);
        int end = arr.length - 1;
        while (end >= 0) {
            swap(arr, 0, end);
            siftDown(0, arr, end);
            end--;
        }
    }

    private void createBigHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(parent, array, array.length);
        }
    }

    private void siftDown(int parent, int[] array, int end) {
        int child = 2 * parent + 1;
        while (child < end) {
            if (child + 1 < end && array[child] < array[child + 1]) {
                child++;
            }
            //child下标 就是左右孩子最大值的下标
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
    private void swap(int[] arr, int minindex, int i) {
        int tmp = arr[minindex];
        arr[minindex] = arr[i];
        arr[i] = tmp;

    }

五、冒泡排序

原理如下:

一趟一趟来,将小的数和大数交换,每一趟都可以将最大的一个数放到最后。所有趟数走完,将排序完成。

 代码思路:

两层循环,第一层控制趟数为arr.length-1,第二层arr.length-1-i表示一趟中交换的次数。定义一个tmp来交换,如果后面的数比前面的数小,则交换,如果大于,就用大于的这个数和后面交换。

优化:可能循环一次就排完序了,剩下的就浪费时间了。我们可以定义一个flg,如果一趟下来都不需要交换,证明完成了,结束2层循环。

插入排序特性总结:

    1. 冒泡排序是一种非常容易理解的排序
    2. 时间复杂度:O(N^2)
    3. 空间复杂度:O(1)
    4. 稳定性:稳定

    //冒泡排序
/*
    1. 冒泡排序是一种非常容易理解的排序
    2. 时间复杂度:O(N^2)
    3. 空间复杂度:O(1)
    4. 稳定性:稳定
*/

    public void buddleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flg = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flg = true;
                }
            }
            if (!flg) {
                break;
            }
        }
    }

六、快速排序

原理如下:

找基准,通常是第一个元素,然后小于它的放左边,大于他的放右边。然后下一组又是这一组的第一个,直到所有元素都排完序。

 代码思路:

1.递归:每次递归都找第一个为基准,然后<基准,放左边;>基准放右边。直到start<end,就排完序。

2.非递归:

  1. 将待排序的序列的首尾元素的下标入栈。
  2. 当栈不为空时,取出栈顶的下标,将序列的首尾元素作为基准值进行分区操作。
  3. 分区操作的目的是将比基准值小的元素放到基准值的左边,比基准值大的元素放到基准值的右边,并返回基准值的下标。
  4. 将分区操作后的左右子序列的首尾元素的下标入栈,注意先将右子序列的下标入栈,再将左子序列的下标入栈。
  5. 重复步骤2-4,直到栈为空。

优化:

1. 三数取中法选key

2. 递归到小的子区间时,可以考虑使用插入排序

插入排序特性总结:

    1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
    2. 时间复杂度:O(N*logN)
    3. 空间复杂度:O(logN)
    4. 稳定性:不稳定

 

 递归

    //快速排序
    /*
    1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
    2. 时间复杂度:O(N*logN)
    3. 空间复杂度:O(logN)
    4. 稳定性:不稳定
*/


    public void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    public void quick(int[] arr, int start, int end) {

        if (start >= end) {
            return;
        }
        if (end - start + 1 <= 10) {
            insertSortRange(arr, start, end);
            return;
        }

        //三数取中(优化)
        int index = midThreeNum(arr, start, end);
        swap(arr, index, start);
        int par = partition(arr, start, end);
        quick(arr, start, par - 1);
        quick(arr, par + 1, end);
    }

    public static void insertSortRange(int[] array, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    public int partitionHoard(int[] arr, int left, int right) {
        int tmp = arr[left];
        int i = left;
        while (left < right) {
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, left, i);
        return left;
    }

    //挖坑法
    public int partition(int[] arr, int left, int right) {
        int tmp = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }

    //返回值是中位数的下标(优化快排)
    private static int midThreeNum(int[] array, int left, int right) {
        int mid = (left + right) / 2;
        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if (array[mid] < array[right]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }

非递归 

   //非递归快速排序
    public void quickSortNor(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = arr.length - 1;
        int par = partition(arr, left, right);
        if (par > left + 1) {
            stack.push(left);
            stack.push(par - 1);
        }
        if (par < right - 1) {
            stack.push(par + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            par = partition(arr, left, right);
            if (par > left + 1) {
                stack.push(left);
                stack.push(par - 1);
            }
            if (par < right - 1) {
                stack.push(par + 1);
                stack.push(right);
            }
        }
    }

七、归并排序

原理如下:

将一组数据递归分成2对,4对....直到分成单一的元素。最后一对一对排序后回来...4对,2对,1对给它排序,直到排完序。

 代码思路:

递归把数据都分成单一的元素,然后合并,合并的话需要创建一个新的数组tmp,定义s1,e1,s2,e2表示分成2份的数组的头和尾,让s1和s2比较,如果s1比s2小,让s1进入tmp数组,否则反之。若一份数组走完了,另一份数组没有,则让另一份数组while循环进入tmp。

插入排序特性总结:

    1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
    2. 时间复杂度:O(N*logN)
    3. 空间复杂度:O(N)
    4. 稳定性:稳定

    //合并排序
/*
    1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
    2. 时间复杂度:O(N*logN)
    3. 空间复杂度:O(N)
    4. 稳定性:稳定
    */
    public void mergeSort(int[] arr) {
        mergeSortFun(arr, 0, arr.length - 1);
    }

    public void mergeSortFun(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (right + left) / 2;
        mergeSortFun(arr, left, mid);
        mergeSortFun(arr, mid + 1, right);
        //合并
        merge(arr, left, mid, right);
    }

    private void merge(int[] arr, int left,
                       int mid, int right) {
        int k = 0;
        int[] tmp = new int[right - left + 1];
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        while (s1 <= e1 && s2 <= e2) {
            if (arr[s1] <= arr[s2]) {
                tmp[k++] = arr[s1++];
            } else {
                tmp[k++] = arr[s2++];
            }
        }
        while (s1 <= e1) {
            tmp[k++] = arr[s1++];
        }
        while (s2 <= e2) {
            tmp[k++] = arr[s2++];
        }
        //拷贝
        for (int i = 0; i < k; i++) {
            arr[i + left] = tmp[i];
        }
    }


    //合并排序非递归
    public void mergeSortNor(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i = i + 2 * gap) {
                int left = i;
                int mid = left + gap - 1;
                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                int right = mid + gap;
                if (right >= array.length) {
                    right = array.length - 1;
                }
                merge(array, left, mid, right);
            }
            gap *= 2;
        }
    }

八、排序总结 

排序方法 最好 平均 最坏 时间复杂度 空间复杂度
冒泡排序 O(N) O(N^2) O(N^2) O(1) 稳定
插入排序 O(N) O(N^2) O(N^2) O(1) 稳定
选择排序 O(N^2) O(N^2) O(N^2) O(1) 不稳定
希尔排序 O(N) O(N^1.3) O(n^2) O(1) 不稳定
堆排序 O(N * log(N)) O(N * log(N)) O(N * log(N)) O(1) 不稳定
快速排序 O(N * log(N)) O(N * log(N)) O(N^2) O(log(N)) ~ O(N) 不稳定
归并排序 O(N * log(N)) O(N * log(N)) O(N * log(N)) O(N) 稳定

额外:计数排序

    //计数排序
/*
    1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
    2. 时间复杂度:O(MAX(N,范围))
    3. 空间复杂度:O(范围)
    4. 稳定性:稳定
    */

    public void countSort(int[] array) {
        //1. 遍历数组 求最大值 和 最小值
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if (maxVal < array[i]) {
                maxVal = array[i];
            }
            if (minVal > array[i]) {
                minVal = array[i];
            }
        }
        //2. 定义count数组
        int[] count = new int[maxVal - minVal + 1];
        //3. 遍历array数组 把值 放入 计数数组当中
        for (int i = 0; i < array.length; i++) {
            int val = array[i];//98
            count[val - minVal]++;
        }
        //4. 以上3步完成之后,计数数组 已经存好了对应的数据
        // 接下来 开始遍历 计数数组
        int index = 0;//array的下标
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                array[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }

上一篇:【JavaEE】AOP实现原理-五.总结


下一篇:chrome扩展清除指定站点缓存chrome.browsingData.remove