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

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

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

 

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

    3187 引用 • 8213 回帖
  • 算法
    428 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • RYMCU

    RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。

    4 引用 • 6 回帖 • 51 关注
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 724 关注
  • 新人

    让我们欢迎这对新人。哦,不好意思说错了,让我们欢迎这位新人!
    新手上路,请谨慎驾驶!

    52 引用 • 228 回帖 • 1 关注
  • 开源

    Open Source, Open Mind, Open Sight, Open Future!

    408 引用 • 3574 回帖
  • RESTful

    一种软件架构设计风格而不是标准,提供了一组设计原则和约束条件,主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁,更有层次,更易于实现缓存等机制。

    30 引用 • 114 回帖 • 2 关注
  • abitmean

    有点意思就行了

    29 关注
  • C

    C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

    85 引用 • 165 回帖 • 2 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    311 引用 • 546 回帖
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    85 引用 • 139 回帖 • 1 关注
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    179 引用 • 407 回帖 • 488 关注
  • GitLab

    GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。

    46 引用 • 72 回帖
  • VirtualBox

    VirtualBox 是一款开源虚拟机软件,最早由德国 Innotek 公司开发,由 Sun Microsystems 公司出品的软件,使用 Qt 编写,在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。

    10 引用 • 2 回帖 • 6 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 47 关注
  • DNSPod

    DNSPod 建立于 2006 年 3 月份,是一款免费智能 DNS 产品。 DNSPod 可以为同时有电信、网通、教育网服务器的网站提供智能的解析,让电信用户访问电信的服务器,网通的用户访问网通的服务器,教育网的用户访问教育网的服务器,达到互联互通的效果。

    6 引用 • 26 回帖 • 510 关注
  • 大数据

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

    93 引用 • 113 回帖
  • TensorFlow

    TensorFlow 是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表示数学操作,图中的线(edges)则表示在节点间相互联系的多维数据数组,即张量(tensor)。

    20 引用 • 19 回帖
  • Sym

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

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

    524 引用 • 4601 回帖 • 700 关注
  • Bug

    Bug 本意是指臭虫、缺陷、损坏、犯贫、窃听器、小虫等。现在人们把在程序中一些缺陷或问题统称为 bug(漏洞)。

    75 引用 • 1737 回帖 • 5 关注
  • 职场

    找到自己的位置,萌新烦恼少。

    127 引用 • 1705 回帖 • 1 关注
  • HBase

    HBase 是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的 Google 论文 “Bigtable:一个结构化数据的分布式存储系统”。就像 Bigtable 利用了 Google 文件系统所提供的分布式数据存储一样,HBase 在 Hadoop 之上提供了类似于 Bigtable 的能力。

    17 引用 • 6 回帖 • 73 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff)、语法高亮、全面的帮助系统、本地脚本(Vimscript)和便于选择的可视化模式。

    29 引用 • 66 回帖
  • ActiveMQ

    ActiveMQ 是 Apache 旗下的一款开源消息总线系统,它完整实现了 JMS 规范,是一个企业级的消息中间件。

    19 引用 • 13 回帖 • 670 关注
  • 导航

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

    40 引用 • 173 回帖
  • 服务

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

    41 引用 • 24 回帖 • 2 关注
  • 锤子科技

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

    4 引用 • 31 回帖 • 4 关注
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 595 关注
  • Hexo

    Hexo 是一款快速、简洁且高效的博客框架,使用 Node.js 编写。

    21 引用 • 140 回帖 • 1 关注