关键词：
package prms.utils.sort;
import java.util.Arrays;
/**
* @ClassName: SortUtils
* @Description: <p> 排序算法 工具类 </p>
* @author edgar
* @email 【[email protected]】
* @version V 1.0
* @date 2017-3-28 15:35:12
*/
public class SortUtils
/**
* @Title: SortUtils
* @Description: 私有化构造 ：类不能实例化
*/
private SortUtils()
public static void main(String[] args)
int[] arr = 2, 5, 3, 1, 4 ;
System.out.println("排序前：" + Arrays.toString(arr));
bubbleSort(arr);
heapSort(arr);
insertSort(arr);
mergeSort(arr);
quickSort(arr);
selectionSort(arr);
shellSort(arr);
System.out.println("排序后：" + Arrays.toString(arr));
/**
* @Title: bubbleSort
* @Description: 冒泡排序
* 依次比较相邻的两个数，将小数放在前面，大数放在后面。
* 即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。
* 然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，
* 直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，
* 将最大的数放到了最后。在第二趟：仍从第一对数开始比较
* （因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），
* 将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），
* 第二趟结束，在倒数第二的位置上得到一个新的最大数
* （其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
* @param data
* @return void
*/
public static void bubbleSort(int[] data)
for (int i = 0; i < data.length - 1; i++)
for (int j = 0; j < data.length - 1 - i; j++)
if (data[j] > data[j + 1])
swap(data, j, j + 1);
/**
* @Title: heapSort
* @Description: 堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征， 使得在当前无序区中选取最大（或最小）关键字的记录变得简单。
* （1）用大根堆排序的基本思想
* ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
* ②再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个 记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，
* 且满足R[1..n-1].keys≤R[n].key ③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。
* 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，
* 由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，
* 且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 直到无序区只有一个元素为止。
* （2）大根堆排序算法的基本操作：
* ① 初始化操作：将R[1..n]构造为初始堆；
* ②每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换， 然后将新的无序区调整为堆（亦称重建堆）。
*
* @param data
* @return void
*/
public static void heapSort(int[] data)
MaxHeap h = new MaxHeap();
h.init(data);
for (int i = 0; i < data.length; i++)
h.remove();
System.arraycopy(h.queue, 1, data, 0, data.length);
private static class MaxHeap
private int size = 0;
private int[] queue;
void init(int[] data)
this.queue = new int[data.length + 1];
for (int i = 0; i < data.length; i++)
queue[++size] = data[i];
fixUp(size);
@SuppressWarnings("unused")
public int get()
return queue[1];
public void remove()
swap(queue, 1, size--);
fixDown(1);
// fixdown
private void fixDown(int k)
int j;
while ((j = k << 1) <= size)
if (j < size && queue[j] < queue[j + 1])
j++;
if (queue[k] > queue[j]) // 不用交换
break;
swap(queue, j, k);
k = j;
private void fixUp(int k)
while (k > 1)
int j = k >> 1;
if (queue[j] > queue[k])
break;
swap(queue, j, k);
k = j;
/**
* @Title: insertSort
* @Description: 插入排序基本思想
* 将n个元素的数列分为已有序和无序两个部分，如插入排序过程示例下所示：
* a1，a2，a3，a4，…，an
* a1⑴，a2⑴，a3⑴，a4⑴ …，an⑴
* a1(n-1），a2(n-1) ，…,an(n-1)
* 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，
* 找出插入位置，将该元素插入到有序数列的合适位置中。
* @param data
* @return void
*/
public static void insertSort(int[] data)
for (int i = 1; i < data.length; i++)
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--)
swap(data, j, j - 1);
/**
* @Title: mergeSort
* @Description: 归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。
* 如设有数列6，202，100，301，38，8，1
* 初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数
* i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3
* i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4
* i=3 [ 1 6 8 38 100 202 301 ] 4
* @param data
* @return void
*/
public static void mergeSort(int[] data)
int[] temp = new int[data.length];
mergeSort(data, temp, 0, data.length - 1);
private static void mergeSort(int[] data, int[] temp, int l, int r)
int mid = (l + r) / 2;
if (l == r)
return;
mergeSort(data, temp, l, mid);
mergeSort(data, temp, mid + 1, r);
for (int i = l; i <= r; i++)
temp[i] = data[i];
int i1 = l;
int i2 = mid + 1;
for (int cur = l; cur <= r; cur++)
if (i1 == mid + 1)
data[cur] = temp[i2++];
else if (i2 > r)
data[cur] = temp[i1++];
else if (temp[i1] < temp[i2])
data[cur] = temp[i1++];
else
data[cur] = temp[i2++];
/**
* @Title: quickSort
* @Description:快速排序
* 一趟快速排序的算法是：
* 1）设置两个变量i、j，排序开始的时候：i=0，j=N-1;
* 2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0];
* 3）从j开始向前搜索，即由后开始向前搜索（j=j-1即j--）,找到第一个小于key的值A[j]，A[i]与A[j]交换；
* 4）从i开始向后搜索，即由前开始向后搜索（i=i+1即i++），找到第一个大于key的A[i]，A[i]与A[j]交换；
* 5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。
* 找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。）
* @param data
* @return void
*/
public static void quickSort(int[] data)
quickSort(data, 0, data.length - 1);
private static void quickSort(int[] data, int i, int j)
int pivotIndex = (i + j) / 2;
// swap
swap(data, pivotIndex, j);
int k = partition(data, i - 1, j, data[j]);
swap(data, k, j);
if ((k - i) > 1)
quickSort(data, i, k - 1);
if ((j - k) > 1)
quickSort(data, k + 1, j);
/**
* @param data
* @param i
* @param j
* @return
*/
private static int partition(int[] data, int l, int r, int pivot)
do
while (data[++l] < pivot);
while ((r != 0) && data[--r] > pivot);
swap(data, l, r);
while (l < r);
swap(data, l, r);
return l;
/**
* @Title: shellSort
* @Description: 希尔排序：
* 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成（n除以d1）个组。所有距离为d1的倍数的记录放在同一个组中。
* 先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，
* 即所有记录放在同一组中进行直接插入排序为止。
*
*
* 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序
* 排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，
* 组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1， 即所有记录放进一个组中排序为止
* 初始：d=5 49 38 65 97 76 13 27 49 55 04
* 49 13 |-------------------|
* 38 27 |-------------------|
* 65 49 |-------------------|
* 97 55 |-------------------|
* 76 04 |-------------------|
* 一趟结果 13 27 49 55 04 49 38 65 97 76
* d=3 13 27 49 55 04 49 38 65 97 76
* 13 55 38 76 |------------|------------|------------|
* 27 04 65 |------------|------------|
* 49 49 97 |------------|------------|
* 二趟结果 13 04 49* 38 27 49 55 65 97 76
* d=1 13 04 49 38 27 49 55 65 97 76
* |----|----|----|----|----|----|----|----|----| 三趟结果
* 04 13 27 38 49 49 55 65 76 97
* @param data
* @return void
*/
public static void shellSort(int[] data)
for (int i = data.length / 2; i > 2; i /= 2)
for (int j = 0; j < i; j++)
insertSort(data, j, i);
insertSort(data, 0, 1);
/**
* @param data
* @param j
* @param i
*/
private static void insertSort(int[] data, int start, int inc)
for (int i = start + inc; i < data.length; i += inc)
for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc)
swap(data, j, j - inc);
/**
* @Title: selectionSort
* @Description: 选择排序基本思路：
* 把第一个元素依次和后面的所有元素进行比较。第一次结束后，就会有最小值出现在最前面。依次类推
* @param data
* @return void
*/
public static void selectionSort(int[] data)
for (int x = 0; x < data.length - 1; x++)
for (int y = x + 1; y < data.length; y++)
if (data[y] < data[x])
swap(data, x, y);
/**
* @Title: swap
* @Description: 交换数组中的两个元素
* @param data
* @param i
* @param j
* @return void
*/
public static void swap(int[] data, int i, int j)
int temp = data[i];
data[i] = data[j];
data[j] = temp;
所有排序算法汇总，冒泡，选择，插入，快速，优化快速，归并，希尔，堆排序
冒泡排序，不多说，两次for循环比较相邻两个元素的大小，然后进行交换。选择排序，我们第一次for循环遍历所有元素，并把当前元素假设为最小的元素，然后再一个for循环去寻找真正最小的元素进行交换，这样每次我们都能找... 查看详情
七种基本排序算法（希尔排序，直接插入排序，冒泡排序，快速排序，简单选择排序，归并排序，堆排序）
classSortAlgorithm{staticvoidMain(string[]args){int[]arr1={1,4,2,7,9,8,3,6};//ShellSort(arr1);//DirectInsertSort(arr1);//BubbleSort(arr1);//QuickSort(arr1,0,arr1.Length-1);//SimpleSelectSort(arr1);//M 查看详情
插入排序（直接插入排序希尔排序）；交换排序（冒泡排序快速排序）；选择排序（简单选择排序堆排序）；归并排序和基数排序；基于关键词比较的排序算法下界分析
文章目录插入排序（直接插入排序、希尔排序）交换排序（冒泡排序、快速排序）选择排序（简单选择排序、堆排序）归并排序和基数排序排序算法分析分治排序的一般方法、基于关键词比较的排序算法下... 查看详情
javascript实现常见排序算法：冒泡，插入，选择，归并，快速，堆排序(代码片段)
1.冒泡排序转自百度百科：冒泡排序，这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名“冒泡排序”。冒泡排序算法的运作如下：（从后往前） 比较相邻的元素。如果第... 查看详情
8大排序算法-我熟知（冒泡直接插入）
分类：1）插入排序（直接插入排序、希尔排序）2）交换排序（冒泡排序、快速排序）3）选择排序（直接选择排序、堆排序）4）归并排序5）分配排序（基数排序）所需辅助空间最多：归并排序所需辅助空间最少：堆排序平均速... 查看详情
冒泡排序，快速排序，归并排序，插入排序，希尔排序，堆排序，计数排序，桶排序，基数排序(代码片段)
选择排序，冒泡排序，快速排序，归并排序，插入排序，希尔排序，计数排序，桶排序，基数排序以上是一些常用的排序算法。选择排序for(inti=0;i<n;i++)intminval=a[i];intminid=i;for(intj=i+1;j<n;j++)if(a[j]<minval)minid=j;minval=a[j];swap(a[i],... 查看详情
python中都有哪些简单的算法？
python中有哪些简单的算法在Python中，Python算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。1、冒泡排序冒泡排序也是一种简单直观的排序算法。重复地走访过要排序的数列，一... 查看详情
数据结构与算法从零开始系列：冒泡排序选择排序插入排序希尔排序堆排序快速排序归并排序基数排序
...都在Github:https://github.com/AndroidHensen/Arithmetic本篇内容包含排序的介绍排序的C的实现排序的Java的实现排序的时间复杂度的计算1、基本思想：两个数比较大小，较大的数下沉，较小的数冒起来2、实现步骤：这张图就是将数字12，35... 查看详情
排序算法时间复杂度o(n^2)冒泡排序选择排序插入排序时间复杂度o(nlogn)快速排序堆排序归并排序其他排序希尔排序计数排序
排序算法时间复杂度o(n^2)冒泡排序选择排序插入排序时间复杂度o(nlogn)快速排序堆排序归并排序其他排序希尔排序计数排序
排序算法python实现
参考技术A排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中... 查看详情
java中8种常见的排序方法
排序方法的演示1）插入排序（直接插入排序、希尔排序）2）交换排序（冒泡排序、快速排序）3）选择排序（直接选择排序、堆排序）4）归并排序5）分配排序（基数排序）所需辅助空间最多：归并排序所需辅助空间最少：堆排... 查看详情
java算法
我们常见的排序分为以下几类：插入排序（直接插入排序，希尔排序）交换排序（冒泡排序，快速排序）选择排序（直接选择排序，堆排序）归并排序分配排序（箱排序，基数排序） 对于以上的排序有什么不同呢？ 需要... 查看详情
内排序方法的比较
内部排序插入排序直接插入排序折半插入排序希尔排序交换排序冒泡排序快速排序选择排序简单选择排序堆排序归并排序基数排序内部排序\\begincases插入排序\\begincases直接插入排序\\\\折半插入排序\\\\希尔排序\\\\\\endcases\\\\\\\\交... 查看详情
常见的排序算法
插入排序直接插入排序，折半插入排序，2-路插入排序，希尔排序快速排序冒泡排序，快速排序（冒泡排序改进），选择排序简单选择排序，树形选择排序，堆排序归并排序基数排序 查看详情
排序算法总结
冒泡排序(交换排序)：大的数右移交换，优化成鸡尾酒排序；演变成快速排序插入排序:从第二个元素往左比较，插入到小于他的数后面希尔排序选择排序：选择最小的放在最左侧，以此类推归并排序：基于分治算法快速排序(交... 查看详情
排序算法
...据结构》简单的把上面的算法总结一下：简单算法：冒泡排序，简单选择排序，直接插入排序改进算法：希尔排序，堆排序，归并排序，快速排序插入排序：直接插入排序和希尔排序交换排序：冒泡排序和快速排序选择排序：简... 查看详情
排序算法小结
排序算法小结排序有可以分为以下几类： (1)、插入排序：直接插入排序、二分法插入排序、希尔排序。 (2)、选择排序：简单选择排序、堆排序。 (3)、交换排序：冒泡排序、快速排序。 (4)、归并排序 (5)、基数... 查看详情