Java实现几种常见排序算法代码-6ren

Java实现几种常见排序算法代码

转载作者：qq735679552 更新时间：2022-09-29 22:32:09

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java实现几种常见排序算法代码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

稳定度（稳定性）一个排序算法是稳定的，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前.

排序算法分类。

常见的有插入（插入排序/希尔排序）、交换（冒泡排序/快速排序）、选择（选择排序）、合并（归并排序）等.

一.插入排序。

插入排序（Insertion Sort），它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间.

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下:

从第一个元素开始，该元素可以认为已经被排序。取出下一个元素，在已经排序的元素序列中从后向前扫描。如果该元素（已排序）大于新元素，将该元素移到下一位置。重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。将新元素插入到该位置后。重复步骤2~5.

复制代码代码如下:

 
 public static void insertionSort(int[] data) { 
 
         for (int index = 1; index < data.length; index++) { 
 
             int key = data[index]; 
 
             int position = index; 
 
             // shift larger values to the right 
 
             while (position > 0 && data[position - 1] > key) { 
 
                 data[position] = data[position - 1]; 
 
                 position--; 
 
             } 
 
             data[position] = key; 
 
         } 
 
     }

二.希尔排序。

。

希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名.

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位.

复制代码代码如下:

 
 static <E extends Comparable<? super E>> void shellSort(List<E> a) { 
 
         int h = 1; 
 
         while (h < a.size()/3) h = h*3 + 1;    // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ... 
 
         for (; h >= 1; h /= 3) 
 
             for (int i = h; i < a.size(); i++) 
 
                 for (int j = i; j >= h && a.get(j).compareTo(a.get(j-h)) < 0; j-=h) 
 
                     Collections.swap(a, j, j-h); 
 
     }

三.冒泡排序。

。

冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端.

冒泡排序算法的运作如下:

比较相邻的元素，如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较.

。

复制代码代码如下:

 
 public static void bubbleSort(int[] data) { 
 
         int temp = 0; 
 
         for (int i = data.length - 1; i > 0; --i) { 
 
             boolean isSort = false; 
 
             for (int j = 0; j < i; ++j) { 
 
                 if (data[j + 1] < data[j]) { 
 
                     temp = data[j]; 
 
                     data[j] = data[j + 1]; 
 
                     data[j + 1] = temp; 
 
                     isSort = true;  
 
                 } 
 
             } 
 
             // 如果一次内循环中发生了交换，那么继续比较；如果一次内循环中没发生任何交换，则认为已经排序好了。 
 
             if (!isSort) 
 
                 break; 
 
         } 
 
     }

四.快速排序。

。

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列.

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）.

步骤为:

从数列中挑出一个元素，称为 "基准"（pivot）。重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序.

。

复制代码代码如下:

/* * more efficient implements for quicksort. * use left, center and right median value (@see #median()) for the pivot, and * the more efficient inner loop for the core of the algorithm. */ public class Quicksort { 。

。

public static final int CUTOFF = 11,

/** * quick sort algorithm. * * @param arr an array of Comparable items. */ public static <T extends Comparable<? super T>> void quicksort(T[] arr) { quickSort(arr, 0, arr.length - 1); } 。

/** * get the median of the left, center and right. * order these and hide the pivot by put it the end of of the array. * * @param arr an array of Comparable items. * @param left the most-left index of the subarray. * @param right the most-right index of the subarray. * @return T */ public static <T extends Comparable<? super T>> T median(T[] arr, int left, int right) { 。

int center = (left + right) / 2,

if (arr[left].compareTo(arr[center]) > 0) swapRef(arr, left, center); if (arr[left].compareTo(arr[right]) > 0) swapRef(arr, left, right); if (arr[center].compareTo(arr[right]) > 0) swapRef(arr, center, right),

swapRef(arr, center, right - 1); return arr[right - 1]; } 。

/** * internal method to sort the array with quick sort algorithm. * * @param arr an array of Comparable Items. * @param left the left-most index of the subarray. * @param right the right-most index of the subarray. */ private static <T extends Comparable<? super T>> void quickSort(T[] arr, int left, int right) { if (left + CUTOFF <= right) { // find the pivot T pivot = median(arr, left, right),

// start partitioning int i = left, j = right - 1; for (;;) { while (arr[++i].compareTo(pivot) < 0); while (arr[--j].compareTo(pivot) > 0); if (i < j) swapRef(arr, i, j); else break; } 。

// swap the pivot reference back to the small collection. swapRef(arr, i, right - 1),

quickSort(arr, left, i - 1); // sort the small collection. quickSort(arr, i + 1, right); // sort the large collection. 。

} else { // if the total number is less than CUTOFF we use insertion sort // instead (cause it much more efficient). insertionSort(arr, left, right); } } 。

/** * method to swap references in an array. * * @param arr an array of Objects. * @param idx1 the index of the first element. * @param idx2 the index of the second element. */ public static <T> void swapRef(T[] arr, int idx1, int idx2) { T tmp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = tmp; } 。

/** * method to sort an subarray from start to end with insertion sort * algorithm. * * @param arr an array of Comparable items. * @param start the begining position. * @param end the end position. */ public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int start, int end) { int i; for (int j = start + 1; j <= end; j++) { T tmp = arr[j]; for (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) { arr[i] = arr[i - 1]; } arr[i] = tmp; } } 。

private static void printArray(Integer[] c) { for (int i = 0; i < c.length; i++) System.out.print(c[i] + ","),

System.out.println(); } 。

public static void main(String[] args) { Integer[] data = {10, 4, 9, 23, 1, 45, 27, 5, 2},

System.out.println("bubbleSort..."); printArray(data); quicksort(data); printArray(data); } } 。

五.选择排序。

。

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕.

因为每一趟确定元素的过程中都会有一个选择最小值的子流程，所以人们形象地称之为选择排序.

举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法.

复制代码代码如下:

 
 public static void selectSort(int[] data) { 
 
         int minIndex = 0; 
 
         int temp = 0; 
 
         for (int i = 0; i < data.length; i++) { 
 
             minIndex = i; // 无序区的最小数据数组下标 
 
             for (int j = i + 1; j < data.length; j++) { // 在无序区中找到最小数据并保存其数组下标 
 
                 if (data[j] < data[minIndex]) { 
 
                     minIndex = j; 
 
                 } 
 
             } 
 
             if (minIndex != i) { // 如果不是无序区的最小值位置不是默认的第一个数据，则交换之。 
 
                 temp = data[i]; 
 
                 data[i] = data[minIndex]; 
 
                 data[minIndex] = temp; 
 
             } 
 
         } 
 
     }

六.归并排序。

。

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用.

归并操作的过程如下:

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。设定两个指针，最初位置分别为两个已经排序序列的起始位置。比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。重复步骤3直到某一指针达到序列尾。将另一序列剩下的所有元素直接复制到合并序列尾.

复制代码代码如下:

public static int[] mergeSort(int[] arr) {// 归并排序 --递归 if (arr.length == 1) { return arr; } int half = arr.length / 2; int[] arr1 = new int[half]; int[] arr2 = new int[arr.length - half]; System.arraycopy(arr, 0, arr1, 0, arr1.length); System.arraycopy(arr, half, arr2, 0, arr2.length); arr1 = mergeSort(arr1); arr2 = mergeSort(arr2); return mergeSortSub(arr1, arr2); } 。

。

private static int[] mergeSortSub(int[] arr1, int[] arr2) {// 归并排序子程序 int[] result = new int[arr1.length + arr2.length]; int i = 0; int j = 0; int k = 0; while (true) { if (arr1[i] < arr2[j]) { result[k] = arr1[i]; if (++i > arr1.length - 1) { break; } } else { result[k] = arr2[j]; if (++j > arr2.length - 1) { break; } } k++; } for (; i < arr1.length; i++) { result[++k] = arr1[i]; } for (; j < arr2.length; j++) { result[++k] = arr2[j]; } return result; } 。

完整代码（除QuickSort）。

复制代码代码如下:

package com.clzhang.sample.thinking,

。

import java.util.*,

/** * 几路常见的排序算法Java实现 * @author acer * */ public class CommonSort { /** * 插入排序具体算法描述如下： * 1.从第一个元素开始，该元素可以认为已经被排序 * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描 * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置 * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 * 5.将新元素插入到该位置后 * 6.重复步骤2~5 */ public static void insertionSort(int[] data) { for (int index = 1; index < data.length; index++) { int key = data[index]; int position = index; // shift larger values to the right while (position > 0 && data[position - 1] > key) { data[position] = data[position - 1]; position--; } data[position] = key; } } /** * 希尔排序，算法实现思想参考维基百科；适合大数量排序操作。 */ static <E extends Comparable<? super E>> void shellSort(List<E> a) { int h = 1; while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ... for (; h >= 1; h /= 3) for (int i = h; i < a.size(); i++) for (int j = i; j >= h && a.get(j).compareTo(a.get(j-h)) < 0; j-=h) Collections.swap(a, j, j-h); } 。

/** * 冒泡排序算法的运作如下： * 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。 * 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 * 3.针对所有的元素重复以上的步骤，除了最后一个。 * 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。[1] */ public static void bubbleSort(int[] data) { int temp = 0; for (int i = data.length - 1; i > 0; --i) { boolean isSort = false; for (int j = 0; j < i; ++j) { if (data[j + 1] < data[j]) { temp = data[j]; data[j] = data[j + 1]; data[j + 1] = temp; isSort = true; } } // 如果一次内循环中发生了交换，那么继续比较；如果一次内循环中没发生任何交换，则认为已经排序好了。 if (!isSort) break; } } /** * 选择排序的基本思想是： * 1.遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 [i+1…n-1] 中找出其中的最小值， * 2.然后将找到的最小值与 i 指向的值进行交换。 * 因为每一趟确定元素的过程中都会有一个选择最小值的子流程，所以人们形象地称之为选择排序。 * @param data */ public static void selectSort(int[] data) { int minIndex = 0; int temp = 0; for (int i = 0; i < data.length; i++) { minIndex = i; // 无序区的最小数据数组下标 for (int j = i + 1; j < data.length; j++) { // 在无序区中找到最小数据并保存其数组下标 if (data[j] < data[minIndex]) { minIndex = j; } } if (minIndex != i) { // 如果不是无序区的最小值位置不是默认的第一个数据，则交换之。 temp = data[i]; data[i] = data[minIndex]; data[minIndex] = temp; } } } /** * 归并操作的过程如下： * 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 * 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置 * 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 * 4.重复步骤3直到某一指针达到序列尾 * 5.将另一序列剩下的所有元素直接复制到合并序列尾 */ public static int[] mergeSort(int[] arr) {// 归并排序 --递归 if (arr.length == 1) { return arr; } int half = arr.length / 2; int[] arr1 = new int[half]; int[] arr2 = new int[arr.length - half]; System.arraycopy(arr, 0, arr1, 0, arr1.length); System.arraycopy(arr, half, arr2, 0, arr2.length); arr1 = mergeSort(arr1); arr2 = mergeSort(arr2); return mergeSortSub(arr1, arr2); } 。

private static void printArray(int[] c) { for (int i = 0; i < c.length; i++) System.out.print(c[i] + ","),

System.out.println(); } public static void main(String []args){ int[] data = {10,4,9,23,1,45,27,5,2}; System.out.println("bubbleSort..."); int[] a = data.clone(); printArray(a); bubbleSort(a); printArray(a),

System.out.println("selectSort..."); int[] b = data.clone(); printArray(b); selectSort(b); printArray(b),

System.out.println("insertionSort..."); int[] c = data.clone(); printArray(c); insertionSort(c); printArray(c),

System.out.println("shellSort..."); List<Integer> list = new ArrayList<Integer>(); for(int i=0;i<data.length;i++) list.add(data[i]); System.out.println(list); shellSort(list); System.out.println(list),

System.out.println("mergeSort..."); int[] d = data.clone(); printArray(d); printArray(mergeSort(d)); } 。

} 。

。

最后此篇关于Java实现几种常见排序算法代码的文章就讲到这里了,如果你想了解更多关于Java实现几种常见排序算法代码的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐：从Nginx切换到Tengine的步骤分享

文章推荐： JAVA中STRING的常用方法小结

文章推荐： try catch finally的执行顺序深入分析

文章推荐： java 获取项目文件路径实现方法

java - 自定义 JPA 实现//现有的无 SQL JPA 实现
背景: 我最近一直在使用 JPA，我为相当大的关系数据库项目生成持久层的轻松程度给我留下了深刻的印象。我们公司使用大量非 SQL 数据库，特别是面向列的数据库。我对可能对这些数据库使用 JPA 有一
java - 未由 S3FileSystem FileSystem 实现 Hadoop Jar 实现
我已经在我的 maven pom 中添加了这些构建配置，因为我希望将 Apache Solr 依赖项与 Jar 捆绑在一起。否则我得到了 SolarServerException: ClassNotF
c# - 实现 "Inherit"(实现)通用接口(interface)的接口(interface)？
interface ITurtle { void Fight(); void EatPizza(); } interface ILeonardo : ITurtle {
java - 任何 JPA 实现(或更广泛的 Java ORM 实现)是否支持可更新游标
我希望可用于 Java 的对象/关系映射 (ORM) 工具之一能够满足这些要求: 使用 JPA 或 native SQL 查询获取大量行并将其作为实体对象返回。允许在行(实体)中进行迭代，并在对当前
generics - 如果我为 B 实现 From ，是否也会为 Vec 实现 From>？
好像没有，因为我有实现From for 的代码, 我可以转换 A到 B与 .into() , 但同样的事情不适用于 Vec .into()一个Vec . 要么我搞砸了阻止实现派生的事情，要么这不应该发

c# - 在 C# 中，如果 A 实现 IX 并且 B 继承自 A ，是否必然遵循 B 实现 IX？
在 C# 中，如果 A 实现 IX 并且 B 继承自 A ，是否必然遵循 B 实现 IX？如果是，是因为 LSP 吗？之间有什么区别吗: 1. Interface IX; Class A : IX;

OpenVG 实现？
就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the

performance - 实现 (^)
我正在阅读标准haskell库的(^)的实现代码: (^) :: (Num a, Integral b) => a -> b -> a x0 ^ y0 | y0 a -> b ->a expo x0

博弈树的C++实现
我将把国际象棋游戏表示为 C++ 结构。我认为，最好的选择是树结构(因为在每个深度我们都有几个可能的移动)。这是一个好的方法吗？ struct TreeElement{ SomeMoveType

字符串匹配alg的c++实现
我正在为用户名数据库实现字符串匹配算法。我的方法采用现有的用户名数据库和用户想要的新用户名，然后检查用户名是否已被占用。如果采用该方法，则该方法应该返回带有数据库中未采用的数字的用户名。例子: “贾

图算法的C++实现
我正在尝试实现 Breadth-first search algorithm , 为了找到两个顶点之间的最短距离。我开发了一个 Queue 对象来保存和检索对象，并且我有一个二维数组来保存两个给定顶点

Python A* 实现
我目前正在 ika 中开发我的 Python 游戏，它使用 python 2.5 我决定为 AI 使用 A* 寻路。然而，我发现它对我的需要来说太慢了(3-4 个敌人可能会落后于游戏，但我想供应 4-

DHT的C++实现
我正在寻找 Kademlia 的开源实现C/C++ 中的分布式哈希表。它必须是轻量级和跨平台的(win/linux/mac)。它必须能够将信息发布到 DHT 并检索它。最佳答案 OpenDHT是

C++实现
我在一本书中读到这一行:-“当我们要求 C++ 实现运行程序时，它会通过调用此函数来实现。” 而且我想知道“C++ 实现”是什么意思或具体是什么。帮忙!？最佳答案 “C++ 实现”是指编译器加上链接

背包分支定界的C++实现
我正在尝试使用分支定界的 C++ 实现这个背包问题。此网站上有一个 Java 版本:Implementing branch and bound for knapsack 我试图让我的 C++ 版本打印

FNV哈希的C#实现
在很多情况下，我需要在 C# 中访问合适的哈希算法，从重写 GetHashCode 到对数据执行快速比较/查找。我发现 FNV 哈希是一种非常简单/好/快速的哈希算法。但是，我从未见过 C# 实现的

LRU缓存替换策略及C#实现
目录 LRU缓存替换策略核心思想不适用场景算法基本实现算法优化

大角度非迭代的空间坐标旋转C#实现
1. 绪论在前面文章中提到空间直角坐标系相互转换，测绘坐标转换时，一般涉及到的情况是：两个直角坐标系的小角度转换。这个就是我们经常在测绘数据处理中，WGS-84坐标系、54北京坐标系

实现.Net7下的数据库定时检查
在软件开发过程中，有时候我们需要定时地检查数据库中的数据，并在发现新增数据时触发一个动作。为了实现这个需求，我们在 .Net 7 下进行一次简单的演示. PeriodicTimer .

查找算法之二分查找的C++实现
二分查找二分查找算法，说白了就是在有序的数组里面给予一个存在数组里面的值key，然后将其先和数组中间的比较，如果key大于中间值，进行下一次mid后面的比较，直到找到相等的，就可以得到它的位置。

qq735679552

个人简介
我是一名优秀的程序员,十分优秀！

作者热门文章

ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机

Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法

在Ubuntu上搭建网桥的方法

ubuntu 虚拟机上网方式及相关配置详解

滴滴打车优惠券免费领取

全站热门文章

深入探讨数据库索引类型：B-tree、Hash、GIN与GiST的对比与应用

HuaweiLiteOS基于Cortex-M4GD32F4平台移植

TensorFlow2入门与实践--CNN

RocketMQ原理—4.消息读写的性能优化

drools规则引擎和solon-flow哪个好？solon-flow简明教程

Winform-耗时操作导致界面渲染滞后

某教育网站疑似删库。。。没备份。。。数据全没了。。。Sealos带你一分钟满血复活

Phi小模型开发教程：C#使用本地模型Phi视觉模型分析图像，实现图片分类、搜索等功能

AQS源码解析

第十二章质量管理(2025年详细解析版）

首页

博学

6Ren·AI

商城

Java实现几种常见排序算法代码