找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

【算法面试】八大常见排序算法(JAVA实现)

admin 2019-4-15 14:13 215人围观 C++相关



概述
排序分为内部排序和外部排序,内部排序是待排序的元素全部放在内存,并在内存中调整它们的顺序。外部排序是部分元素放到内存中,在内外存间调整元素的顺序。我们通常说的八大排序直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序、堆排序、归并排序、基数排序都是内部排序,下面来具体介绍这八种排序的如何用Java实现,以及它们所需的时间复杂度和空间复杂度。

直接插入排序
基本思想:将一个待排序的元素插入到已经排好序的序列中,如果待排序的元素与有序序列的中的某个元素相等,则把待排序元素插到该元素后面。

算法实现:
    publicstaticvoidinsertSort(int[] element) {for (int i = 1; i < element.length; i++) {int tmp = element[i];int j = i -1;for (; j >= 0; j--) {if (tmp < element[j]) { element[j + 1] = element[j]; } else {break; } }//正确的插入位置是:j+1 element[j+1] = tmp; } }

    时间复杂度:
    直接插入排序是稳定的排序,其时间复杂度是O(n^2)。
    说明:稳定的排序是指相等的元素经过排序后,其相对位置没有发生改变。
    说明:如果待排序的元素是正序(从小到大排列),每插入一个元素只需比较一次,这样时间复杂度就是O(n)。反之,如果待排序的元素是逆序(从大到小排列),当插入第i个元素时,需要比较i次,这样时间复杂度是O(n^2)。

    希尔排序
    基本思想:

    希尔排序实质上是一种分组插入排序,其先将整个待排元素序列分割成若干个子序列(由距离为d的元素组成)分别进行直接插入排序,然后依次减少距离d再进行排序,当距离为1时,再对全体元素进行一次直接插入排序。
    算法实现:
      publicstaticvoidhellSort(int[] element){int d = element.length;while (true){ d = d/2;for(int i = 0; i < d; i++){for(int j = i+d; j < element.length; j+=d){int tmp = element[j];int k = j-d;for(;k >= 0; k-=d){if(tmp < element[k]){ element[k + d ] = element[k]; }else{break; } } element[k + d] = tmp; } }if(d == 1) break; } }

      时间复杂度:
      希尔排序中相同的元素可能在各自组的插入排序中移动,最后其稳定性会被打乱,所以希尔排序是不稳定的,其时间复杂度是O(nlogn)。

      简单选择排序
      基本思想:

      在n个待排序的元素中找取最小的元素与第一个元素交换位置,然后在n-1个元素中找取最小的元素与第二元素交换位置,直到n=1为止。
      算法实现:
        publicstaticvoidselectSort(int[] element){int minPos;int tmp;for(int i = 0 ; i < element.length; i++ ){ minPos = i;for(int j = i+1; j < element.length; j++){if(element[j] < element[minPos]){ minPos = j; } } tmp = element[minPos]; element[minPos] = element[i]; element[i] = tmp; } }

        时间复杂度:
        简单选择排序是不稳定的排序,其时间复杂度是O(n^2)。
        不稳定说明:
        假设待排元素序列是:6,4,6,7,2,9,第一次排序后,序列变成了2,4,6,7,6,9,我们可以发现,经过一次排序后,位置一的6调整到位置三的6的后面,所以简单选择排序是不稳定的排序。

        冒泡排序
        基本思想:

        从待排序元素的倒数第一位开始向前遍历,如果当前元素比前面元素小,则交换位置。这样一次遍历下来,最小的元素冒泡到第一个位置了,然后,从倒数第二位、第三位...开始向前遍历,重复上面的过程,直到元素有序。
        算法实现:
          publicstaticvoidbubbleSort(int[] element){int tmp;int len = element.length;for(int i = 0; i < len; i++ ) {for (int j = len -1; j - 1 >= i; j--) {if (element[j] < element[j - 1]) { tmp = element[j]; element[j] = element[j - 1]; element[j - 1] = tmp; } } } }

          时间复杂度:
          冒泡排序是稳定的排序,时间复杂度是O(n^2)。

          快速排序
          基本思想:

          选择一个基准元素(通常选择第一个元素或者最后一个元素),通过一次排序将待排序列分为两部分,一部分都比基准元素小,另一部分都比基准元素大,然后再按此方法对这两组数据分别进行快速排序,直到待排序列有序。
          算法实现:
            publicstaticvoidquickSort(int[] element, int low, int high) {if (low < high) {int mid = partition(element, low, high); quickSort(element, low, mid - 1); quickSort(element, mid + 1, high); } }

            publicstaticintpartition(int[] element, int low, int high){int baseElement = element[low];
            while (low < high) {while (low < high && baseElement <= element[high]) high--; element[low] = element[high];while (low < high && baseElement >= element[low]) low++; element[high] = element[low]; } element[low] = baseElement;return low; }

            时间复杂度:
            快速排序是不稳定排序,时间复杂度是O(nlogn)。

            堆排序
            基本思想:

            堆的概念:
            n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系之一时,称之为堆。
              情形1:ki <= k2i 且ki <= k2i+1 (最小堆)
              情形2:ki >= k2i 且ki >= k2i+1 (最大堆)
              其中i=1,2,…,n/2向下取整;
            堆排序:
            把待排序的序列看作是一棵顺序存储的二叉树,调整它们的存储顺序,使之成为一个最大堆,这时堆的根节点数最大。然后,将根节点与堆的最后一个节点交换,并对前面n-1个数重新调整使之成为堆,依此类推,最后得到有n个节点的有序序列。
            从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆结果。
            说明:若想得到升序序列,则建立最大堆,若想得到降序序列,则建立最小堆。
            算法实现:
              publicstaticvoidheapSort(int[] element) {//step1:建堆int length = element.length;for (int i = length / 2 - 1; i >= 0; i--) { adjustHeap(element, i, length - 1); }//step2:交换位置,调整堆结构int tmp;for (int j = length - 1; j >= 0; j--) { tmp = element[j]; element[j] = element[0]; element[0] = tmp; adjustHeap(element, 0, j - 1); } }
              publicstaticvoidadjustHeap(int[] element, int start, int end) {int tmp = element[start];for (int i = 2 * start + 1; i <= end; i = 2 * i + 1) {//定位父节点的左右孩子值较大的节点if (i < end && element[i] < element[i + 1]) { i++; }//父节点比左右孩子值都大,则跳出循环if (tmp > element[i]) {break; }//进行下一轮的筛选 element[start] = element[i]; start = i; } element[start] = tmp; }

              时间复杂度:
              堆排序是不稳定的排序,其时间复杂度是O(nlogn)。

              归并排序
              基本思想:

              是把待排序序列分为若干个子序列,每个子序列是有序的,然后再把有序子序列合并为整体有序序列。
              算法实现:
                publicstatic void mergeSort(int[] element, int left, int right) {if (left < right) { int mid = (left + right) / 2;//左边进行递归排序 mergeSort(element, left, mid);//右边进行递归排序 mergeSort(element, mid + 1, right);//左右两部分进行合并处理 merge(element, left, mid, right); } }

                publicstatic void merge(int[] element, int left, int middle, int right) { int[] tmpElement = new int[element.length]; int index = left; int mid = middle + 1; int tmpIndex = left;while (left <= middle && mid <= right) {if (element[left] < element[mid]) { tmpElement[index++] = element[left++]; } else { tmpElement[index++] = element[mid++]; } }while (left <= middle) { tmpElement[index++] = element[left++]; }while (mid <= right) { tmpElement[index++] = element[mid++]; }
                while (tmpIndex <= right){ element[tmpIndex] = tmpElement[tmpIndex ++]; } }

                时间复杂度:
                归并排序是稳定的排序,其时间复杂度为O(nlogn)。

                字基数排序
                基本思想:

                将所有待排序列(正整数)统一为同样的数位长度,数位较短的数前面补零。然后 ,从最低位开始,依次进行一次排序。这样,从最低位一直到最高位排序完成以后, 数列就变成一个有序序列。

                算法实现:

                  publicstaticvoidradixSort(int[] number, int d) //d表示最大的数有多少位 {int k = 0;int n = 1;int m = 1; //控制键值排序依据在哪一位int[][] temp = newint[10][number.length]; //数组的第一维表示可能的余数0-9int[] order = newint[10]; //数组orderp[i]用来表示该位是i的数的个数while (m <= d) {for (int i = 0; i < number.length; i++) {int lsd = ((number[i] / n) % 10); temp[lsd][order[lsd]] = number[i]; order[lsd]++; }for (int i = 0; i < 10; i++) {if (order[i] != 0)for (int j = 0; j < order[i]; j++) { number[k] = temp[i][j]; k++; } order[i] = 0; } n *= 10; k = 0; m++; } }

                  时间复杂度:
                  基数排序是稳定的排序,其时间复杂度为O(d(n+r)),d为位数,r为基数范围。

                  附:八大排序的时间复杂度、空间复杂度、稳定性



                  历史推荐

                  【算法面试】常见动态规划算法示例1-最长公共子串问题

                  【算法面试】算术表达式计算

                  【算法面试】判断括号序列是否合法









                  ----------------------------------------------------------------------------------------------------------------------
                  我们尊重原创,也注重分享,文章来源于微信公众号:程序员面试经验分享,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
                  ----------------------------------------------------------------------------------------------------------------------

                  鲜花

                  握手

                  雷人

                  路过

                  鸡蛋

                  yafeilinux和他的朋友们微信公众号二维码

                  微信公众号

                  专注于Qt嵌入式Linux开发等。扫一扫立即关注。

                  Qt开源社区官方QQ群二维码

                  QQ交流群

                  欢迎加入QQ群大家庭,一起讨论学习!

                  我有话说......