Java 版七种排序算法代码大全

本贴最后更新于 3157 天前,其中的信息可能已经沧海桑田

冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序(冒择入希快归堆)

 

Java版代码:

 

package com.kevin;

 

/**

 * 七种排序算法Java版

 *

 * @author Administrator

 *

 */

public class Sort {

 

   /**

    * 打印数组

    *

    * @param data

    */

   public static void displayData(int[] data) {

      for (int d : data) {

         System.out.print(d + " ");

      }

      System.out.println();

   }

 

   /**

    * 冒泡排序算法,时间复杂度O(n2),算法具有稳定性,堆排序和快速排序算法不具有稳定性,即排序后相同元素的顺序会发生变化

    *

    * @param src

    */

   public static void bubbleSort(int[] src) {

      if (src.length > 0) {

         int length = src.length;

         for (int i = 1; i < length; i++) {

            for (int j = 0; j < length - i; j++) {

                if (src[j] > src[j + 1]) {

                   int temp = src[j];

                   src[j] = src[j + 1];

                   src[j + 1] = temp;

                }

            }

         }

      }

   }

 

   /**

    * 快速排序,时间复杂度O(nlogn),最坏时间复杂度O(n2),平均时间复杂度O(nlogn),算法不具稳定性

    *

    * @param src

    * @param begin

    * @param end

    */

   public static void quickSort(int[] src, int begin, int end) {

      if (begin < end) {

         int key = src[begin];

         int i = begin;

         int j = end;

 

         while (i < j) {

            while (i < j && src[j] > key) {

                j--;

            }

            if (i < j) {

                src[i] = src[j];

                i++;

            }

            while (i < j && src[i] < key) {

                i++;

            }

            if (i < j) {

                src[j] = src[i];

                j--;

            }

         }

 

         src[i] = key;

 

         quickSort(src, begin, i - 1);

         quickSort(src, i + 1, end);

      }

 

   }

 

   /**

    * 选择排序,分为简单选择排序、树形选择排序(锦标赛排序)、堆排序 此算法为简单选择排序

    *

    * @param a

    */

   public static void selectSort(int[] a) {

      int length = a.length;

      for (int i = 0; i < length; i++) {

         int minIndex = i;

        

         for (int j = i + 1; j < a.length; j++) {

            if (a[j] < a[minIndex]) {

                minIndex = j;

            }

         }

        

         if (minIndex != i) {

            int temp = a[minIndex];

            a[minIndex] = a[i];

            a[i] = temp;

         }

      }

   }

 

   /**

    * 插入排序,适用于少量数据的排序,时间复杂度O(n2),是稳定的排序算法,原地排序

    *

    * @param a

    */

   public static void insertSort(int[] a) {

      int length = a.length;

 

      for (int i = 1; i < length; i++) {

         int temp = a[i];

         int j = i;

         for (; j > 0 && a[j - 1] > temp; j--) {

            a[j] = a[j - 1];

         }

         a[j] = temp;

      }

   }

 

   /**

    * 归并排序算法,稳定排序,非原地排序,空间复杂度O(n),时间复杂度O(nlogn)

    *

    * @param a

    * @param low

    * @param high

    */

   public static void mergeSort(int a[], int low, int high) {

      if (low < high) {

         mergeSort(a, low, (low + high) / 2);

         mergeSort(a, (low + high) / 2 + 1, high);

         merge(a, low, (high + low) / 2, high);

      }

   }

 

   /**

    * 归并排序辅助方法,合并

    *

    * @param a

    * @param low

    * @param mid

    * @param high

    */

   private static void merge(int[] a, int low, int mid, int high) {

      int[] b = new int[high - low + 1];

      int s = low;

      int t = mid + 1;

      int k = 0;

      while (s <= mid && t <= high) {

         if (a[s] <= a[t])

            b[k++] = a[s++];

         else

            b[k++] = a[t++];

      }

      while (s <= mid)

         b[k++] = a[s++];

      while (t <= high)

         b[k++] = a[t++];

      for (int i = 0; i < b.length; i++) {

         a[low + i] = b[i];

      }

   }

 

   /**

    * 希尔排序的一种实现方法

    *

    * @param a

    */

   public static void shellSort(int[] a) {

      int temp;

      for (int k = a.length / 2; k > 0; k /= 2) {

         for (int i = k; i < a.length; i++) {

            for (int j = i; j >= k; j -= k) {

                if (a[j - k] > a[j]) {

                   temp = a[j - k];

                   a[j - k] = a[j];

                   a[j] = temp;

                }

            }

         }

      }

   }

 

   /**

    * 堆排序,最坏时间复杂度O(nlog2n),平均性能接近于最坏性能。由于建初始堆所需的比较次数多,故堆不适合记录较少的比较 堆排序为原地不稳定排序

    *

    * @param array

    */

   public static void heapSort(int[] array) {

      for (int i = 1; i < array.length; i++) {

         makeHeap(array, i);

      }

 

      for (int i = array.length - 1; i > 0; i--) {

         int temp = array[i];

         array[i] = array[0];

         array[0] = temp;

         rebuildHeap(array, i);

      }

   }

 

   /**

    * 堆排序辅助方法---创建堆

    *

    * @param array

    * @param k

    */

   private static void makeHeap(int[] array, int k) {

      int current = k;

      while (current > 0 && array[current] > array[(current - 1) / 2]) {

         int temp = array[current];

         array[current] = array[(current - 1) / 2];

         array[(current - 1) / 2] = temp;

         current = (current - 1) / 2;

      }

 

   }

 

   /**

    * 堆排序辅助方法---堆的根元素已删除,末尾元素已移到根位置,开始重建

    *

    * @param array

    * @param size

    */

   private static void rebuildHeap(int[] array, int size) {

      int currentIndex = 0;

      int right = currentIndex * 2 + 2;

      int left = currentIndex * 2 + 1;

      int maxIndex = currentIndex;

      boolean isHeap = false;

      while (!isHeap) {

         if (left < size && array[currentIndex] < array[left]) {

            maxIndex = left;

         }

         if (right < size && array[maxIndex] < array[right]) {

            maxIndex = right;

         }

         if (currentIndex == maxIndex) {

            isHeap = true;

         } else {

            int temp = array[currentIndex];

            array[currentIndex] = array[maxIndex];

            array[maxIndex] = temp;

            currentIndex = maxIndex;

            right = currentIndex * 2 + 2;

            left = currentIndex * 2 + 1;

         }

      }

   }

 

   public static void main(String[] args) {

      int data[] = { 2, -1, 5, 4, 6, 8, 7, -3 };

      Sort.displayData(data);

     

      Sort.bubbleSort(data);

      Sort.displayData(data);

   }

 

}

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3190 引用 • 8214 回帖 • 1 关注
  • 算法
    428 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • 微信

    腾讯公司 2011 年 1 月 21 日推出的一款手机通讯软件。用户可以通过摇一摇、搜索号码、扫描二维码等添加好友和关注公众平台,同时可以将自己看到的精彩内容分享到微信朋友圈。

    132 引用 • 795 回帖
  • 国际化

    i18n(其来源是英文单词 internationalization 的首末字符 i 和 n,18 为中间的字符数)是“国际化”的简称。对程序来说,国际化是指在不修改代码的情况下,能根据不同语言及地区显示相应的界面。

    8 引用 • 26 回帖
  • 负能量

    上帝为你关上了一扇门,然后就去睡觉了....努力不一定能成功,但不努力一定很轻松 (° ー °〃)

    88 引用 • 1235 回帖 • 402 关注
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 9 关注
  • Pipe

    Pipe 是一款小而美的开源博客平台。Pipe 有着非常活跃的社区,可将文章作为帖子推送到社区,来自社区的回帖将作为博客评论进行联动(具体细节请浏览 B3log 构思 - 分布式社区网络)。

    这是一种全新的网络社区体验,让热爱记录和分享的你不再感到孤单!

    132 引用 • 1114 回帖 • 122 关注
  • WebClipper

    Web Clipper 是一款浏览器剪藏扩展,它可以帮助你把网页内容剪藏到本地。

    3 引用 • 9 回帖 • 2 关注
  • SpaceVim

    SpaceVim 是一个社区驱动的模块化 vim/neovim 配置集合,以模块的方式组织管理插件以
    及相关配置,为不同的语言开发量身定制了相关的开发模块,该模块提供代码自动补全,
    语法检查、格式化、调试、REPL 等特性。用户仅需载入相关语言的模块即可得到一个开箱
    即用的 Vim-IDE。

    3 引用 • 31 回帖 • 109 关注
  • 单点登录

    单点登录(Single Sign On)是目前比较流行的企业业务整合的解决方案之一。SSO 的定义是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。

    9 引用 • 25 回帖 • 2 关注
  • 微软

    微软是一家美国跨国科技公司,也是世界 PC 软件开发的先导,由比尔·盖茨与保罗·艾伦创办于 1975 年,公司总部设立在华盛顿州的雷德蒙德(Redmond,邻近西雅图)。以研发、制造、授权和提供广泛的电脑软件服务业务为主。

    8 引用 • 44 回帖
  • CSDN

    CSDN (Chinese Software Developer Network) 创立于 1999 年,是中国的 IT 社区和服务平台,为中国的软件开发者和 IT 从业者提供知识传播、职业发展、软件开发等全生命周期服务,满足他们在职业发展中学习及共享知识和信息、建立职业发展社交圈、通过软件开发实现技术商业化等刚性需求。

    14 引用 • 155 回帖
  • 运维

    互联网运维工作,以服务为中心,以稳定、安全、高效为三个基本点,确保公司的互联网业务能够 7×24 小时为用户提供高质量的服务。

    149 引用 • 257 回帖 • 2 关注
  • SendCloud

    SendCloud 由搜狐武汉研发中心孵化的项目,是致力于为开发者提供高质量的触发邮件服务的云端邮件发送平台,为开发者提供便利的 API 接口来调用服务,让邮件准确迅速到达用户收件箱并获得强大的追踪数据。

    2 引用 • 8 回帖 • 490 关注
  • ngrok

    ngrok 是一个反向代理,通过在公共的端点和本地运行的 Web 服务器之间建立一个安全的通道。

    7 引用 • 63 回帖 • 625 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    190 引用 • 1057 回帖
  • ZooKeeper

    ZooKeeper 是一个分布式的,开放源码的分布式应用程序协调服务,是 Google 的 Chubby 一个开源的实现,是 Hadoop 和 HBase 的重要组件。它是一个为分布式应用提供一致性服务的软件,提供的功能包括:配置维护、域名服务、分布式同步、组服务等。

    59 引用 • 29 回帖 • 9 关注
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    343 引用 • 723 回帖
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖
  • 星云链

    星云链是一个开源公链,业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎,一个公链的所有功能,它基本都有,比如你可以用它来开发部署你的去中心化的 APP,你可以在上面编写智能合约,发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖 • 1 关注
  • 锤子科技

    锤子科技(Smartisan)成立于 2012 年 5 月,是一家制造移动互联网终端设备的公司,公司的使命是用完美主义的工匠精神,打造用户体验一流的数码消费类产品(智能手机为主),改善人们的生活质量。

    4 引用 • 31 回帖
  • IDEA

    IDEA 全称 IntelliJ IDEA,是一款 Java 语言开发的集成环境,在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品,这家公司总部位于捷克共和国的首都布拉格,开发人员以严谨著称的东欧程序员为主。

    181 引用 • 400 回帖
  • 大数据

    大数据(big data)是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。

    93 引用 • 113 回帖
  • 黑曜石

    黑曜石是一款强大的知识库工具,支持本地 Markdown 文件编辑,支持双向链接和关系图。

    A second brain, for you, forever.

    16 引用 • 130 回帖
  • App

    App(应用程序,Application 的缩写)一般指手机软件。

    91 引用 • 384 回帖
  • FlowUs

    FlowUs.息流 个人及团队的新一代生产力工具。

    让复杂的信息管理更轻松、自由、充满创意。

    1 引用
  • 代码片段

    代码片段分为 CSS 与 JS 两种代码,添加在 [设置 - 外观 - 代码片段] 中,这些代码会在思源笔记加载时自动执行,用于改善笔记的样式或功能。

    用户在该标签下分享代码片段时需在帖子标题前添加 [css] [js] 用于区分代码片段类型。

    93 引用 • 624 回帖
  • 互联网

    互联网(Internet),又称网际网络,或音译因特网、英特网。互联网始于 1969 年美国的阿帕网,是网络与网络之间所串连成的庞大网络,这些网络以一组通用的协议相连,形成逻辑上的单一巨大国际网络。

    98 引用 • 344 回帖
  • SQLServer

    SQL Server 是由 [微软] 开发和推广的关系数据库管理系统(DBMS),它最初是由 微软、Sybase 和 Ashton-Tate 三家公司共同开发的,并于 1988 年推出了第一个 OS/2 版本。

    21 引用 • 31 回帖