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

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

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

 

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

    3165 引用 • 8206 回帖 • 1 关注
  • 算法
    388 引用 • 254 回帖 • 22 关注

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • Swift

    Swift 是苹果于 2014 年 WWDC(苹果开发者大会)发布的开发语言,可与 Objective-C 共同运行于 Mac OS 和 iOS 平台,用于搭建基于苹果平台的应用程序。

    34 引用 • 37 回帖 • 495 关注
  • 服务器

    服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。

    124 引用 • 580 回帖
  • Git

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

    204 引用 • 357 回帖 • 1 关注
  • Sublime

    Sublime Text 是一款可以用来写代码、写文章的文本编辑器。支持代码高亮、自动完成,还支持通过插件进行扩展。

    10 引用 • 5 回帖 • 1 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 498 关注
  • 自由行
  • 京东

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

    14 引用 • 102 回帖 • 406 关注
  • Ruby

    Ruby 是一种开源的面向对象程序设计的服务器端脚本语言,在 20 世纪 90 年代中期由日本的松本行弘(まつもとゆきひろ/Yukihiro Matsumoto)设计并开发。在 Ruby 社区,松本也被称为马茨(Matz)。

    7 引用 • 31 回帖 • 166 关注
  • SMTP

    SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议,它是一组用于由源地址到目的地址传送邮件的规则,由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。

    4 引用 • 18 回帖 • 581 关注
  • flomo

    flomo 是新一代 「卡片笔记」 ,专注在碎片化时代,促进你的记录,帮你积累更多知识资产。

    3 引用 • 74 回帖 • 3 关注
  • 安装

    你若安好,便是晴天。

    128 引用 • 1183 回帖
  • 外包

    有空闲时间是接外包好呢还是学习好呢?

    26 引用 • 232 回帖 • 17 关注
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用,而且功能强大。你无需专门学习,只需看上几眼,就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 591 关注
  • MongoDB

    MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。

    90 引用 • 59 回帖 • 5 关注
  • Facebook

    Facebook 是一个联系朋友的社交工具。大家可以通过它和朋友、同事、同学以及周围的人保持互动交流,分享无限上传的图片,发布链接和视频,更可以增进对朋友的了解。

    4 引用 • 15 回帖 • 448 关注
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    41 引用 • 130 回帖 • 294 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    28 引用 • 108 回帖 • 3 关注
  • 周末

    星期六到星期天晚,实行五天工作制后,指每周的最后两天。再过几年可能就是三天了。

    14 引用 • 297 回帖
  • 链书

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

    链书社

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

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

    Markdown 是一种轻量级标记语言,用户可使用纯文本编辑器来排版文档,最终通过 Markdown 引擎将文档转换为所需格式(比如 HTML、PDF 等)。

    163 引用 • 1446 回帖 • 1 关注
  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    324 引用 • 1395 回帖
  • ZooKeeper

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

    59 引用 • 29 回帖 • 18 关注
  • Postman

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

    4 引用 • 3 回帖
  • TGIF

    Thank God It's Friday! 感谢老天,总算到星期五啦!

    284 引用 • 4481 回帖 • 652 关注
  • 智能合约

    智能合约(Smart contract)是一种旨在以信息化方式传播、验证或执行合同的计算机协议。智能合约允许在没有第三方的情况下进行可信交易,这些交易可追踪且不可逆转。智能合约概念于 1994 年由 Nick Szabo 首次提出。

    1 引用 • 11 回帖 • 6 关注
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 34 关注
  • OnlyOffice
    4 引用 • 19 关注