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

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

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

 

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 回帖
  • 算法
    388 引用 • 254 回帖 • 22 关注

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • Swift

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

    34 引用 • 37 回帖 • 496 关注
  • 招聘

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

    189 引用 • 1056 回帖
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    10 引用 • 54 回帖 • 125 关注
  • ReactiveX

    ReactiveX 是一个专注于异步编程与控制可观察数据(或者事件)流的 API。它组合了观察者模式,迭代器模式和函数式编程的优秀思想。

    1 引用 • 2 回帖 • 124 关注
  • Bootstrap

    Bootstrap 是 Twitter 推出的一个用于前端开发的开源工具包。它由 Twitter 的设计师 Mark Otto 和 Jacob Thornton 合作开发,是一个 CSS / HTML 框架。

    18 引用 • 33 回帖 • 683 关注
  • Mobi.css

    Mobi.css is a lightweight, flexible CSS framework that focus on mobile.

    1 引用 • 6 回帖 • 689 关注
  • frp

    frp 是一个可用于内网穿透的高性能的反向代理应用,支持 TCP、UDP、 HTTP 和 HTTPS 协议。

    15 引用 • 7 回帖
  • 笔记

    好记性不如烂笔头。

    303 引用 • 777 回帖
  • BookxNote

    BookxNote 是一款全新的电子书学习工具,助力您的学习与思考,让您的大脑更高效的记忆。

    笔记整理交给我,一心只读圣贤书。

    1 引用 • 1 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    261 引用 • 662 回帖 • 1 关注
  • wolai

    我来 wolai:不仅仅是未来的云端笔记!

    1 引用 • 11 回帖
  • Ruby

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

    7 引用 • 31 回帖 • 166 关注
  • 数据库

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

    330 引用 • 614 回帖
  • C++

    C++ 是在 C 语言的基础上开发的一种通用编程语言,应用广泛。C++ 支持多种编程范式,面向对象编程、泛型编程和过程化编程。

    106 引用 • 152 回帖 • 2 关注
  • Facebook

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

    4 引用 • 15 回帖 • 449 关注
  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权,因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 3 关注
  • SQLite

    SQLite 是一个进程内的库,实现了自给自足的、无服务器的、零配置的、事务性的 SQL 数据库引擎。SQLite 是全世界使用最为广泛的数据库引擎。

    4 引用 • 7 回帖 • 1 关注
  • 安全

    安全永远都不是一个小问题。

    189 引用 • 813 回帖 • 2 关注
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    534 引用 • 671 回帖
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    5 引用 • 13 回帖
  • SMTP

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

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

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖 • 1 关注
  • 倾城之链
    23 引用 • 66 回帖 • 93 关注
  • Electron

    Electron 基于 Chromium 和 Node.js,让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目,兼容 Mac、Windows 和 Linux,它构建的应用可在这三个操作系统上面运行。

    15 引用 • 136 回帖
  • jQuery

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

    63 引用 • 134 回帖 • 744 关注
  • RIP

    愿逝者安息!

    8 引用 • 92 回帖 • 285 关注
  • 国际化

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

    7 引用 • 26 回帖 • 1 关注