## 常用排序算法 原

王孟君

Arrays工具类包含了对各种类型数组的排序，以下是Arrays中包括的sort方法：

``````/**
* Sorts the specified list into ascending order, according to the
* <i>natural ordering</i> of its elements.  All elements in the list must
* implement the <tt>Comparable</tt> interface.  Furthermore, all elements
* in the list must be <i>mutually comparable</i> (that is,
* <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
* for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
*
* This sort is guaranteed to be <i>stable</i>:  equal elements will
* not be reordered as a result of the sort.<p>
*
* The specified list must be modifiable, but need not be resizable.<p>
*
* The sorting algorithm is a modified mergesort (in which the merge is
* omitted if the highest element in the low sublist is less than the
* lowest element in the high sublist).  This algorithm offers guaranteed
* n log(n) performance.
*
* This implementation dumps the specified list into an array, sorts
* the array, and iterates over the list resetting each element
* from the corresponding position in the array.  This avoids the
* n<sup>2</sup> log(n) performance that would result from attempting
* to sort a linked list in place.
*
* @param  list the list to be sorted.
* @throws ClassCastException if the list contains elements that are not
*	       <i>mutually comparable</i> (for example, strings and integers).
* @throws UnsupportedOperationException if the specified list's
*	       list-iterator does not support the <tt>set</tt> operation.
* @see Comparable
*/
public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}

/**
* Sorts the specified list according to the order induced by the
* specified comparator.  All elements in the list must be <i>mutually
* comparable</i> using the specified comparator (that is,
* <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
* for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
*
* This sort is guaranteed to be <i>stable</i>:  equal elements will
* not be reordered as a result of the sort.<p>
*
* The sorting algorithm is a modified mergesort (in which the merge is
* omitted if the highest element in the low sublist is less than the
* lowest element in the high sublist).  This algorithm offers guaranteed
* n log(n) performance.
*
* The specified list must be modifiable, but need not be resizable.
* This implementation dumps the specified list into an array, sorts
* the array, and iterates over the list resetting each element
* from the corresponding position in the array.  This avoids the
* n<sup>2</sup> log(n) performance that would result from attempting
* to sort a linked list in place.
*
* @param  list the list to be sorted.
* @param  c the comparator to determine the order of the list.  A
*        <tt>null</tt> value indicates that the elements' <i>natural
*        ordering</i> should be used.
* @throws ClassCastException if the list contains elements that are not
*	       <i>mutually comparable</i> using the specified comparator.
* @throws UnsupportedOperationException if the specified list's
*	       list-iterator does not support the <tt>set</tt> operation.
* @see Comparator
*/
public static <T> void sort(List<T> list, Comparator<? super T> c) {
Object[] a = list.toArray();
Arrays.sort(a, (Comparator)c);
ListIterator i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set(a[j]);
}
}``````

## 常用排序

``````package my.sort;

public abstract class BaseSort<T> {

@SuppressWarnings("hiding")
protected abstract <T extends Comparable<T>> void sort(T[] array);

@SuppressWarnings({ "hiding" })
protected <T extends Comparable<T>> boolean lessThan(T t1, T t2) {
return t1.compareTo(t2) < 0;
}

@SuppressWarnings({ "hiding" })
protected <T extends Comparable<T>> boolean greatThan(T t1, T t2) {
return t1.compareTo(t2) > 0;
}

@SuppressWarnings("hiding")
protected <T extends Comparable<T>> boolean equalTo(T t1, T t2) {
return t1.compareTo(t2) == 0;
}

@SuppressWarnings("hiding")
protected <T extends Comparable<T>> void swap(T[] array, int i, int j) {
T t = array[i];
array[i] = array[j];
array[j] = t;
}

@SuppressWarnings("hiding")
protected <T extends Comparable<T>> void printArray(T[] array) {
for (T t : array) {
System.out.print(t);
System.out.print(" ");
}
System.out.println();
}

}``````

### 冒泡排序

``````package my.sort;

public class BubbleSort<T> extends BaseSort<T> {

@SuppressWarnings("hiding")
@Override
protected <T extends Comparable<T>> void sort(T[] array) {
int length = array.length;
for (int i = 0; i < length; i++) {
for (int j = 1; j < length - i; j++) {
if (greatThan(array[j - 1], array[j])) {
swap(array, j - 1, j);
}
}
}
}
}``````

### 插入排序

``````package my.sort;

public class InsertionSort<T> extends BaseSort<T> {

@SuppressWarnings("hiding")
@Override
protected <T extends Comparable<T>> void sort(T[] array) {
int length = array.length;
for (int i = 1; i < length; i++) {
for (int j = i; j > 0 && lessThan(array[j], array[j - 1]); j--) {
swap(array, j, j - 1);
}
}
}
}``````

### 选择排序

``````package my.sort;

public class SelectionSort<T> extends BaseSort<T> {

@SuppressWarnings("hiding")
@Override
protected <T extends Comparable<T>> void sort(T[] array) {
int length = array.length;
for (int i = 0; i < length; i++) {
int min = i;
for (int j = i + 1; j < length; j++) {
if (lessThan(array[j], array[min])) {
min = j;
}
}
swap(array, i, min);
}
}

}``````

### 希尔排序

``````package my.sort;

public class ShellSort<T> extends BaseSort<T> {

@SuppressWarnings("hiding")
@Override
protected <T extends Comparable<T>> void sort(T[] array) {
int length = array.length;
int h = 1;
while (h < length / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h && lessThan(array[j], array[j - h]); j -= h) {
swap(array, j, j - h);
}
}
h /= 3;
}

}

}``````

### 快速排序

``````package my.sort;

public class QuickSort<T> extends BaseSort<T> {

@SuppressWarnings("hiding")
@Override
protected <T extends Comparable<T>> void sort(T[] array) {
sort(array, 0, array.length - 1);
}

@SuppressWarnings("hiding")
private <T extends Comparable<T>> void sort(T[] array, int low, int high) {
if (high <= low)
return;
int j = partition(array, low, high);
sort(array, low, j - 1);
sort(array, j + 1, high);
}

@SuppressWarnings("hiding")
private <T extends Comparable<T>> int partition(T[] array, int low, int high) {
int i = low;
int j = high + 1;

T v = array[low];

while (true) {
while (lessThan(array[++i], v)) {
if (i == high)
break;
}

while (lessThan(v, array[--j])) {
if (j == low)
break;
}

if (i >= j)
break;

swap(array, i, j);
}

swap(array, low, j);

return j;

}
}``````

### 归并排序

``````package my.sort;

/**
* 自顶向下的归并排序
*
* @author Eric
* @param <T>
*/
public class MergeSort<T> extends BaseSort<T> {

@SuppressWarnings("unchecked")
private Comparable[] aux = null; // 归并所需的辅助数组

@SuppressWarnings("hiding")
@Override
protected <T extends Comparable<T>> void sort(T[] array) {
int length = array.length;
aux = new Comparable[length];
doSort(array, 0, length - 1);

}

@SuppressWarnings("hiding")
private <T extends Comparable<T>> void doSort(T[] array, int low, int high) {
if (low < high) {

// 找出中间索引
int mid = low + (high - low) / 2;

// 对左边数组进行递归
doSort(array, low, mid);

// 对右边数组进行递归
doSort(array, mid + 1, high);

// 合并
doMerge(array, low, mid, high);
}

}

@SuppressWarnings( { "hiding", "unchecked" })
private <T extends Comparable<T>> void doMerge(T[] array, int low, int mid,
int high) {
// 将array[low...mid]和[mid+1...high]归并
int i = low;
int j = mid + 1;

/* 将array[low...high]复制到aux[low...high] */
for (int k = low; k <= high; k++) {
aux[k] = array[k];
}

for (int k = low; k <= high; k++) {
if (i > mid) {
array[k] = (T) aux[j++];
} else if (j > high) {
array[k] = (T) aux[i++];
} else if (lessThan(aux[j], aux[i])) {
array[k] = (T) aux[j++];
} else {
array[k] = (T) aux[i++];
}
}
}

/*	public static void main(String[] args) {

String[] array = { "Hello", "World", "Eric", "Allen" };
MergeSort<String> sort = new MergeSort<String>();
sort.printArray(array);
sort.sort(array);
sort.printArray(array);
}*/

}``````

### 堆排序

``````package my.sort;

public class HeapSort<T> extends BaseSort<T> {

@SuppressWarnings("hiding")
@Override
protected <T extends Comparable<T>> void sort(T[] array) {

int length = array.length;

buildHeap(array, length);

while (length > 1) {
length--;
swap(array, 0, length);
downHeap(array, length, 0);
}

}

@SuppressWarnings("hiding")
private <T extends Comparable<T>> void buildHeap(T[] array, int length) {
for (int v = length / 2 - 1; v >= 0; v--) {
downHeap(array, length, v);
}
}

@SuppressWarnings("hiding")
private <T extends Comparable<T>> void downHeap(T[] array, int length, int v) {

int w = 2 * v + 1;
while (w < length) {

if ((w + 1 < length) && greatThan(array[w + 1], array[w])) {
w++;
}

if (!lessThan(array[v], array[w])) {
return;
}
swap(array, v, w);
v = w;
w = 2 * v + 1;

}
}

}``````

## 排序比较

### 王孟君

#### 暂无文章

50分钟前
0
0

Part1实现一个基本的区块链 1.区块链 区块链是由一个个任何人都可以访问的区块构成的公共数据库。这好像没什么特别的，不过它们有一个有趣的属性：它们是不可变的。一旦一个区块被添加到区块...

54分钟前
1
0
HTTP协议

HTTP简介 HTTP协议是Hyper Text Transfer Protocol（超文本传输协议）的缩写,是用于从万维网（WWW:World Wide Web ）服务器传输超文本到本地浏览器的传送协议。 HTTP是一个基于TCP/IP通信协议...

56分钟前
1
0
Feign输出Info级别日志

xiaomin0322

3
0

1、start一个spring boot项目 第一课我们也不能免俗，要从starter开始，spring boot的起始项目脚手架可以从spring boot官方starter生成地址开始：https://start.spring.io/ 这张图列出了一个...

wphmoon

3
0