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

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

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

 

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 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3201 引用 • 8217 回帖 • 2 关注
  • 算法
    424 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    589 引用 • 3528 回帖
  • 反馈

    Communication channel for makers and users.

    120 引用 • 906 回帖 • 277 关注
  • ngrok

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

    7 引用 • 63 回帖 • 655 关注
  • Git

    Git 是 Linux Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。

    211 引用 • 358 回帖
  • 区块链

    区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。所谓共识机制是区块链系统中实现不同节点之间建立信任、获取权益的数学算法 。

    92 引用 • 752 回帖 • 2 关注
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    240 引用 • 224 回帖
  • 深度学习

    深度学习(Deep Learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。

    43 引用 • 44 回帖
  • Openfire

    Openfire 是开源的、基于可拓展通讯和表示协议 (XMPP)、采用 Java 编程语言开发的实时协作服务器。Openfire 的效率很高,单台服务器可支持上万并发用户。

    6 引用 • 7 回帖 • 121 关注
  • WebComponents

    Web Components 是 W3C 定义的标准,它给了前端开发者扩展浏览器标签的能力,可以方便地定制可复用组件,更好的进行模块化开发,解放了前端开发者的生产力。

    1 引用 • 9 关注
  • CodeMirror
    2 引用 • 17 回帖 • 171 关注
  • RemNote
    2 引用 • 16 回帖 • 24 关注
  • 强迫症

    强迫症(OCD)属于焦虑障碍的一种类型,是一组以强迫思维和强迫行为为主要临床表现的神经精神疾病,其特点为有意识的强迫和反强迫并存,一些毫无意义、甚至违背自己意愿的想法或冲动反反复复侵入患者的日常生活。

    15 引用 • 161 回帖
  • 京东

    京东是中国最大的自营式电商企业,2015 年第一季度在中国自营式 B2C 电商市场的占有率为 56.3%。2014 年 5 月,京东在美国纳斯达克证券交易所正式挂牌上市(股票代码:JD),是中国第一个成功赴美上市的大型综合型电商平台,与腾讯、百度等中国互联网巨头共同跻身全球前十大互联网公司排行榜。

    14 引用 • 102 回帖 • 311 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 562 关注
  • sts
    2 引用 • 2 回帖 • 241 关注
  • GitHub

    GitHub 于 2008 年上线,目前,除了 Git 代码仓库托管及基本的 Web 管理界面以外,还提供了订阅、讨论组、文本渲染、在线文件编辑器、协作图谱(报表)、代码片段分享(Gist)等功能。正因为这些功能所提供的便利,又经过长期的积累,GitHub 的用户活跃度很高,在开源世界里享有深远的声望,并形成了社交化编程文化(Social Coding)。

    209 引用 • 2040 回帖
  • Kubernetes

    Kubernetes 是 Google 开源的一个容器编排引擎,它支持自动化部署、大规模可伸缩、应用容器化管理。

    118 引用 • 54 回帖 • 3 关注
  • 书籍

    宋真宗赵恒曾经说过:“书中自有黄金屋,书中自有颜如玉。”

    82 引用 • 412 回帖
  • 链书

    链书(Chainbook)是 B3log 开源社区提供的区块链纸质书交易平台,通过 B3T 实现共享激励与价值链。可将你的闲置书籍上架到链书,我们共同构建这个全新的交易平台,让闲置书籍继续发挥它的价值。

    链书社

    链书目前已经下线,也许以后还有计划重制上线。

    14 引用 • 257 回帖 • 1 关注
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 728 关注
  • 星云链

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

    3 引用 • 16 回帖 • 1 关注
  • 七牛云

    七牛云是国内领先的企业级公有云服务商,致力于打造以数据为核心的场景化 PaaS 服务。围绕富媒体场景,七牛先后推出了对象存储,融合 CDN 加速,数据通用处理,内容反垃圾服务,以及直播云服务等。

    29 引用 • 230 回帖 • 124 关注
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4601 回帖 • 709 关注
  • 导航

    各种网址链接、内容导航。

    45 引用 • 177 回帖
  • Firefox

    Mozilla Firefox 中文俗称“火狐”(正式缩写为 Fx 或 fx,非正式缩写为 FF),是一个开源的网页浏览器,使用 Gecko 排版引擎,支持多种操作系统,如 Windows、OSX 及 Linux 等。

    7 引用 • 30 回帖 • 378 关注
  • Java

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

    3201 引用 • 8217 回帖 • 2 关注
  • Webswing

    Webswing 是一个能将任何 Swing 应用通过纯 HTML5 运行在浏览器中的 Web 服务器,详细介绍请看 将 Java Swing 应用变成 Web 应用

    1 引用 • 15 回帖 • 643 关注