Java数据结构的十大排序

Java数据结构的十大排序

目录1.直接插入排序1.1 动图演示1.2 插入排序的思路1.3 代码实现1.4 性能分析2.希尔排序2.1 原理2.2 动图演示2.3 代码实现2.4 性能分析3.直接选择排序3.1 动图演示3.2 代码实现3.3 性能分析4.堆排序4.1 动图演示4.2 代码实现4.3 性能分析5.冒泡排序5.1 动图演示5.2 代码实现5.3 性能分析6.快速排序6.1 原理6.2 动图演示6.3 实现方法6.3.1 Hoare法6.3.2 挖坑法6.4 代码实现6.5 快排优化6.5.1 三数取中法6.5.2 加上直接插入排序6.6 非递归的实现6.6.1 非递归思路6.6.2 非递归代码实现6.7 性能分析7.归并排序7.1 原理7.2 动图演示7.3 代码实现—递归7.4 代码实现—非递归7.5 性能分析8.计数排序8.1 算法的步骤8.2 动图演示8.3 代码实现8.4 性能分析9.桶排序9.1 原理9.2 算法的步骤9.3 画图解析9.4 代码实现9.5 性能分析10.基数排序10.1 算法的步骤10.2 动图演示10.3 代码实现10.4 性能分析

1.直接插入排序

1.1 动图演示

1.2 插入排序的思路

从第一个元素开始,这里我们第一个元素是已排序的.取下一个元素,和有序序列的元素从后往前比较.( 有序区间 : [0,i) )如果得到的有序序列的元素 比 该元素大 则 将取得的有序元素往后放重复3操作,直到得到的有序元素 比 该元素小, 或者 有序元素比完了.记录这个位置然后将该元素放入到这个位置.遍历数组,重复2~5的操作.

1.3 代码实现

/**

* 时间复杂度:

* 最好的情况: O(n)

* 最坏的情况: O(n^2)

* 空间复杂度: O(1)

* @param array

*/

public static void insertSort(int[] array) {

for (int i = 1; i < array.length; i++) {

int j = i - 1;

int tmp = array[i];

while (j >= 0) {

if (array[j] > tmp) {

array[j + 1] = array[j];

j--;

}else {

break;

}

}

array[j + 1] = tmp;

}

}

1.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^2)O(n^2)O(n)O(1)稳定

插入排序，初始数据越接近有序，时间效率越高。

2.希尔排序

2.1 原理

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成个gap组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取gap = (gap/3)+1，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

希尔排序是对直接插入排序的优化。当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

2.2 动图演示

2.3 代码实现

/**

*

* @param array 排序的数组

* @param gap 每组的间隔 -> 数组

*/

public static void shell(int[] array,int gap){

for (int i = gap; i < array.length ; i++) {

int tmp = array[i];

int j = i - gap;

while(j>=0){

if(array[j] > tmp){

array[j + gap] = array[j];

j -= gap;

}else {

break;

}

}

array[j + gap] = tmp;

}

}

public static void shellSort(int[] array){

int gap = array.length;

while (gap > 1){

gap = (gap / 3) + 1;// +1 保证最后一个序列是 1 (除几都行)

shell(array,gap);

}

}

2.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^1.3)O(n^2)O(n)O(1)不稳定

3.直接选择排序

3.1 动图演示

3.2 代码实现

/**

* 时间复杂度:

* 最好: O(n^2)

* 最坏: O(n^2)

* 空间复杂度: O(1)

* 稳定性: 不稳定

* @param array

*/

public static void selectSort(int[] array){

for (int i = 0; i < array.length - 1; i++) {

for (int j = i + 1; j

if(array[j] < array[i]){

int tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

}

}

}

3.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^2)O(n^2)O(n^2)O(1)不稳定

4.堆排序

4.1 动图演示

4.2 代码实现

public static void siftDown(int[] array,int root, int len){

int parent = root;

int child = root * 2 + 1;

while (child < len){

if( child+1 < len && array[child] < array[child+1] ){

child++;

}

//这里child下标就是左右孩子的最大值的下标

if(array[child] > array[parent]){

int tmp = array[child];

array[child] = array[parent];

array[parent] = tmp;

parent = child;

child = parent * 2 + 1;

}else {

break;

}

}

}

public static void createHeap(int[] array){

for (int i = (array.length - 1 - 1) / 2; i >= 0; i++) {

siftDown(array,i,array.length);

}

}

public static void heapSort(int[] array){

createHeap(array);

int end = array.length - 1;

while (end > 0){

int tmp = array[end];

array[end] = array[0];

array[0] =tmp;

siftDown(array,0,end);

end--;

}

}

4.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n * log(n))O(n * log(n))O(n * log(n))O(1)不稳定

5.冒泡排序

5.1 动图演示

5.2 代码实现

public static void BubbleSort(int[] array){

for (int i = 0; i < array.length - 1; i++) {

boolean flg = false;

for (int j = 0; j < array.length - 1 - i ; j++) {

if(array[j+1] < array[j]){

int tmp = array[j];

array[j] = array[j+1];

array[j+1] = tmp;

flg = true;

}

}

if(!flg){

break;

}

}

}

5.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^2)O(n^2)O(n)O(1)稳定

6.快速排序

6.1 原理

从待排序区间选择一个数，作为基准值(pivot)；Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。

6.2 动图演示

6.3 实现方法

6.3.1 Hoare法

6.3.2 挖坑法

6.4 代码实现

//Hoare法

public static void swap(int[] array,int i,int j){

int tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

public static int partition1(int[] array,int low,int high) {

int i = low;

int tmp = array[low];

while (low < high){

while (low < high && array[high] >= tmp){

high--;

}

while (low < high && array[low] <= tmp){

low++;

}

swap(array,low,high);

}

swap(array,i,low);

return low;

}

//挖坑法

public static int partition2(int[] array,int low,int high) {

int tmp = array[low];

while (low < high){

while (low < high && array[high] >= tmp){

high--;

}

array[low] = array[high];

TLrDZeUrj while (low < high && array[low] <= tmp){

low++;

}

array[high] = array[low];

}

array[low] = tmp;

return low;

}

public static void quick(int[] array,int start,int end){

if(start >= end) return;

int pivot = partition1(array,start,end);

quick(array,start,pivot-1);

quick(array,pivot+1,end);

}

public static void quickSort(int[] array){

quick(array,0,array.length-1);

}

6.5 快排优化

6.5.1 三数取中法

public static void swap(int[] array,int i,int j){

int tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

public static int partition2(int[] array,int low,int high) {

int tmp = array[low];

while (low < high){

while (low < high && array[high] >= tmp){

high--;

}

array[low] = array[high];

while (low < high && array[low] <= tmp){

low++;

}

array[high] = array[low];

}

array[low] = tmp;

return low;

}

public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){

if(array[mid] > array[start]){

swap(array,start,mid);

}//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]

if(array[mid] > array[end]){

swap(array,mid,end);

}//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]

if(array[start] > array[end]){

swap(array,start,end);

}//此时有 array[mid] <= array[start] <= array[end]

}

public static void quick1(int[] array,int start,int end){

if(start >= end) return;

int mid = (start + end) / 2;

selectPivotMedianOFThree(array,start,end,mid);

int pivot = partition2(array,start,end);

quick1(array,start,pivot-1);

quick1(array,pivot+1,end);

}

public static void quick1Sort(int[] array){

quick1(array,0,array.length - 1);

}

6.5.2 加上直接插入排序

public static void swap(int[] array,int i,int j){

int tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

public static void insertSort2(int[] array,int start,int end){

for (int i = start + 1; i <= end; i++) {

int j = i + 1;

int tmp = array[i];

while (j >= 0){

if(array[j] > tmp){

array[j+1] = array[j];

}else {

break;

}

}

array[j+1] = tmp;

}

}

public static int partition2(int[] array,int low,int high) {

int tmp = array[low];

while (low < high){

while (low < high && array[high] >= tmp){

high--;

}

array[low] = array[high];

while (low < high && array[low] <= tmp){

low++;

}

array[high] = array[low];

}

array[low] = tmp;

return low;

}

public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){

if(array[mid] > array[start]){

swap(array,start,mid);

}//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]

if(array[mid] > array[end]){

swap(array,mid,end);

}//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]

if(array[start] > array[end]){

swap(array,start,end);

}//此时有 array[mid] <= array[start] <= array[end]

}

public static void quick2(int[] array,int start,int end){

if(start >= end) return;

if(end - start + 1 <= 100){

insertSort2(array,start,end);

return;

}

int mid = (start + end)/2;

selectPivotMedianOFThree(array,start,end,mid);

int pivot = partition2(array,start,end);

quick2(array,start,pivot-1);

quick2(array,pivot+1,end);

}

public static void quick2Sort(int[] array){

quick2(array,0,array.length - 1);

}

6.6 非递归的实现

6.6.1 非递归思路

首先调用partition,找到pivot然后把pivot的 左区间 和 右区间 的下标放到栈立马判断栈是否为空,不为空,弹出栈顶的2个元素(注意:入栈的顺序 决定了出栈的顺序中的第一个元素是high的还是low的)然后再进行调用partition,找pivot,重复以上操作.

6.6.2 非递归代码实现

public static void quickSort4(int[] array){

Stack stack = new Stack<>();

int low = 0;

int high = array.length - 1;

int pivot = partition2(array,low ,high);

//左边有2个元素即以上

if(pivot > low + 1){

stack.push(0);

stack.push(pivot - 1);

}

//右边有2个元素即以上

if(pivot < high - 1){

stack.push(pivot + 1);

stack.push(high);

}

while (!stack.isEmpty()){

high = stack.pop();

low = stack.pop();

pivot = partition2(array,low,high);

//左边有2个元素即以上

if(pivot > low + 1){

stack.push(0);

stack.push(pivot - 1);

}

//右边有2个元素即以上

if(pivot < high - 1){

stack.push(pivot + 1);

stack.push(high);

}

}

}

6.7 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n * log(n))O(n^2)O(n * log(n))O(log(n))~O(n)不稳定

7.归并排序

7.1 原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子 序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

7.2 动图演示

7.3 代码实现—递归

public static void merge(int[] array,int low ,int high ,int mid){

int s1 = low;

int e1 = mid;

int s2 = mid+1;

int e2 = high;

int[] tmp = new int[high - low + 1];

int k = 0;

while (s1 <= e1 && s2 <= e2){

if(array[s1] <= array[s2]){

tmp[k++] = array[s1++];

}else {

tmp[k++] = array[s2++];

}

}

while (s1 <= e1){

tmp[k++] = array[s1++];

}

while (s2 <= e2){

tmp[k++] = array[s2++];

}

for (int i = 0; i < tmp.length; i++) {

array[i+low] = tmp[i];

}

}

public static void mergeSortInternal(int[] array,int low ,int high){

if(low >= high) return;

int mid = (low + high) / 2;

mergeSortInternal(array,low,mid);

mergeSortInternal(array,mid+1,high);

merge(array,low,high,mid);

}

public static void mergeSort(int[] array){

mergeSortInternal(array,0,array.length - 1);

}

7.4 代码实现—非递归

public static void merge1(int[] array,int gap){

int[] tmp = new int[array.length];

int k = 0;

int s1 = 0;

int e1 = s1 + gap - 1;

int s2 = e1 + 1;

int e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1;

while (s2 < array.length){

while (s1 <= e1 && s2 <= e2){

if(array[s1] <= array[s2]){

tmp[k++] = array[s1++];

}else {

tmp[k++] = array[s2++];

}

}

while (s1 <= e1){

tmp[k++] = array[s1++];

}

while (s2 <= e2){

tmp[k++] = array[s2++];

}

s1 = e2 + 1;

e1 = s1 + gap - 1;

s2 = e1 + 1;

e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1;

}

while (s1 <= array.length - 1){

tmp[k++] = array[s1++];

}

for (int i = 0; i < tmp.length; i++) {

array[i] = tmp[i];

}

}

public static void mergeSort1(int[] array){

for (int i = 1; i < array.length; i*=2) {

merge1(array,i);

}

}

7.5 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n * log(n))O(n * log(n))O(n * log(n))O(n)稳定

8.计数排序

当输入的元素是 n 个 0 到 k 之间的整数时，它的运http://行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

8.1 算法的步骤

（1）找出待排序的数组中最大和最小的元素（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

8.2 动图演示

8.3 代码实现

public static void CountingSort(int[] array){

int maxValue = GetMaxValue(array);

int bucketLen = maxValue + 1;

int[] bucket = new int[bucketLen];

for (int value:array) {

bucket[value]++;

}

int index = 0 ;

for (int i = 0; i < bucketLen; i++) {

while(bucket[i] > 0){

array[index++] = i;

bucket[i]--;

}

}

}

public static int GetMaxValue(int[] array){

int maxValue = array[0];

for (int i = 0; i < array.length; i++) {

if(maxValue < array[i]){

maxValue = array[i];

}

}

return maxValue;

}

8.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n+k)O(n+k)O(n+k)O(k)稳定

9.桶排序

9.1 原理

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

9.2 算法的步骤

设置一个定量的数组当作空桶；遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序；从不是空的桶里把排好序的数据拼接起来。

9.3 画图解析

9.4 代码实现

public static void bucketSort(int[] arr) {

if (arr.length == 0) {

return;

}

int minValue = arr[0];

int maxValue = arr[0];

for (int value : arr) {

if (value < minValue) {

minValue = value;

} else if (value > maxValue) {

maxValue = value;

}

}

//得到最大和最小元素

int bucketNum = (maxValue - minValue) / arr.length + 1;//桶的数量

ArrayList> bucket = new ArrayList<>(bucketNum);

for (int i = 0; i < bucketNum; i++) {

bucket.add(new ArrayList<>());

}

//将元素放入到桶中

for (int i = 0; i < arr.length; i++) {

int num = (arr[i] - minValue) / arr.length;

bucket.get(num).add(arr[i]);

}

for (int i = 0; i < bucket.size(); i++) {

//这里是比较,可以选择其他的方式实现,这里为了演示TLrDZeUrj采取Collection的sort

Collections.sort(bucket.get(i));

}

// 将桶中的元素赋值到原序列

int index = 0;

for(int i = 0; i < bucket.size(); i++){

for(int j = 0; j < bucket.get(i).size(); j++){

arr[index++] = bucket.get(i).get(j);

}

}

}

9.5 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n+k)O(n^2)O(n+k)O(n+k)稳定

10.基数排序

10.1 算法的步骤

取得数组中的最大数，并取得位数；arr为原始数组，从最低位开始取每个位组成radix数组；对radix进行计数排序（利用计数排序适用于小范围数的特点）

10.2 动图演示

10.3 代码实现

public static int getNumLength(int num){

if(num == 0) return 1;

int count = 0;

for (int i = num; i != 0; i /= 10) {

count++;

}

return count;

}

public static void RadixSort(int[] array){

int maxValue = array[0];

for (int i = 0; i < array.length; i++) {

if(maxValue < array[i]){

maxValue = array[i];

}

}

int maxDigit = getNumLength(maxValue);

int mod = 10;

int dev = 1;

for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {

int[][] counter = new int[mod * 2][0];

for (int j = 0; j < array.length; j++) {

int bucket = ((array[j] % mod) / dev) + mod;

counter[bucket] = arrayAppend(counter[bucket], array[j]);

}

int pos = 0;

for (int[] bucket : counter) {

for (int value : bucket) {

array[pos++] = value;

}

}

}

}

public static inTLrDZeUrjt[] arrayAppend(int[] arr, int value) {

arr = Arrays.copyOf(arr, arr.length + 1);

arr[arr.length - 1] = value;

return arr;

}

10.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n*k)O(n*2)O(n*k)O(n+k)稳定

总结：

if(array[j] < array[i]){

int tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

}

}

}

3.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^2)O(n^2)O(n^2)O(1)不稳定

4.堆排序

4.1 动图演示

4.2 代码实现

public static void siftDown(int[] array,int root, int len){

int parent = root;

int child = root * 2 + 1;

while (child < len){

if( child+1 < len && array[child] < array[child+1] ){

child++;

}

//这里child下标就是左右孩子的最大值的下标

if(array[child] > array[parent]){

int tmp = array[child];

array[child] = array[parent];

array[parent] = tmp;

parent = child;

child = parent * 2 + 1;

}else {

break;

}

}

}

public static void createHeap(int[] array){

for (int i = (array.length - 1 - 1) / 2; i >= 0; i++) {

siftDown(array,i,array.length);

}

}

public static void heapSort(int[] array){

createHeap(array);

int end = array.length - 1;

while (end > 0){

int tmp = array[end];

array[end] = array[0];

array[0] =tmp;

siftDown(array,0,end);

end--;

}

}

4.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n * log(n))O(n * log(n))O(n * log(n))O(1)不稳定

5.冒泡排序

5.1 动图演示

5.2 代码实现

public static void BubbleSort(int[] array){

for (int i = 0; i < array.length - 1; i++) {

boolean flg = false;

for (int j = 0; j < array.length - 1 - i ; j++) {

if(array[j+1] < array[j]){

int tmp = array[j];

array[j] = array[j+1];

array[j+1] = tmp;

flg = true;

}

}

if(!flg){

break;

}

}

}

5.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^2)O(n^2)O(n)O(1)稳定

6.快速排序

6.1 原理

从待排序区间选择一个数，作为基准值(pivot)；Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。

6.2 动图演示

6.3 实现方法

6.3.1 Hoare法

6.3.2 挖坑法

6.4 代码实现

//Hoare法

public static void swap(int[] array,int i,int j){

int tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

public static int partition1(int[] array,int low,int high) {

int i = low;

int tmp = array[low];

while (low < high){

while (low < high && array[high] >= tmp){

high--;

}

while (low < high && array[low] <= tmp){

low++;

}

swap(array,low,high);

}

swap(array,i,low);

return low;

}

//挖坑法

public static int partition2(int[] array,int low,int high) {

int tmp = array[low];

while (low < high){

while (low < high && array[high] >= tmp){

high--;

}

array[low] = array[high];

TLrDZeUrj while (low < high && array[low] <= tmp){

low++;

}

array[high] = array[low];

}

array[low] = tmp;

return low;

}

public static void quick(int[] array,int start,int end){

if(start >= end) return;

int pivot = partition1(array,start,end);

quick(array,start,pivot-1);

quick(array,pivot+1,end);

}

public static void quickSort(int[] array){

quick(array,0,array.length-1);

}

6.5 快排优化

6.5.1 三数取中法

public static void swap(int[] array,int i,int j){

int tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

public static int partition2(int[] array,int low,int high) {

int tmp = array[low];

while (low < high){

while (low < high && array[high] >= tmp){

high--;

}

array[low] = array[high];

while (low < high && array[low] <= tmp){

low++;

}

array[high] = array[low];

}

array[low] = tmp;

return low;

}

public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){

if(array[mid] > array[start]){

swap(array,start,mid);

}//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]

if(array[mid] > array[end]){

swap(array,mid,end);

}//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]

if(array[start] > array[end]){

swap(array,start,end);

}//此时有 array[mid] <= array[start] <= array[end]

}

public static void quick1(int[] array,int start,int end){

if(start >= end) return;

int mid = (start + end) / 2;

selectPivotMedianOFThree(array,start,end,mid);

int pivot = partition2(array,start,end);

quick1(array,start,pivot-1);

quick1(array,pivot+1,end);

}

public static void quick1Sort(int[] array){

quick1(array,0,array.length - 1);

}

6.5.2 加上直接插入排序

public static void swap(int[] array,int i,int j){

int tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

public static void insertSort2(int[] array,int start,int end){

for (int i = start + 1; i <= end; i++) {

int j = i + 1;

int tmp = array[i];

while (j >= 0){

if(array[j] > tmp){

array[j+1] = array[j];

}else {

break;

}

}

array[j+1] = tmp;

}

}

public static int partition2(int[] array,int low,int high) {

int tmp = array[low];

while (low < high){

while (low < high && array[high] >= tmp){

high--;

}

array[low] = array[high];

while (low < high && array[low] <= tmp){

low++;

}

array[high] = array[low];

}

array[low] = tmp;

return low;

}

public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){

if(array[mid] > array[start]){

swap(array,start,mid);

}//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]

if(array[mid] > array[end]){

swap(array,mid,end);

}//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]

if(array[start] > array[end]){

swap(array,start,end);

}//此时有 array[mid] <= array[start] <= array[end]

}

public static void quick2(int[] array,int start,int end){

if(start >= end) return;

if(end - start + 1 <= 100){

insertSort2(array,start,end);

return;

}

int mid = (start + end)/2;

selectPivotMedianOFThree(array,start,end,mid);

int pivot = partition2(array,start,end);

quick2(array,start,pivot-1);

quick2(array,pivot+1,end);

}

public static void quick2Sort(int[] array){

quick2(array,0,array.length - 1);

}

6.6 非递归的实现

6.6.1 非递归思路

首先调用partition,找到pivot然后把pivot的 左区间 和 右区间 的下标放到栈立马判断栈是否为空,不为空,弹出栈顶的2个元素(注意:入栈的顺序 决定了出栈的顺序中的第一个元素是high的还是low的)然后再进行调用partition,找pivot,重复以上操作.

6.6.2 非递归代码实现

public static void quickSort4(int[] array){

Stack stack = new Stack<>();

int low = 0;

int high = array.length - 1;

int pivot = partition2(array,low ,high);

//左边有2个元素即以上

if(pivot > low + 1){

stack.push(0);

stack.push(pivot - 1);

}

//右边有2个元素即以上

if(pivot < high - 1){

stack.push(pivot + 1);

stack.push(high);

}

while (!stack.isEmpty()){

high = stack.pop();

low = stack.pop();

pivot = partition2(array,low,high);

//左边有2个元素即以上

if(pivot > low + 1){

stack.push(0);

stack.push(pivot - 1);

}

//右边有2个元素即以上

if(pivot < high - 1){

stack.push(pivot + 1);

stack.push(high);

}

}

}

6.7 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n * log(n))O(n^2)O(n * log(n))O(log(n))~O(n)不稳定

7.归并排序

7.1 原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子 序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

7.2 动图演示

7.3 代码实现—递归

public static void merge(int[] array,int low ,int high ,int mid){

int s1 = low;

int e1 = mid;

int s2 = mid+1;

int e2 = high;

int[] tmp = new int[high - low + 1];

int k = 0;

while (s1 <= e1 && s2 <= e2){

if(array[s1] <= array[s2]){

tmp[k++] = array[s1++];

}else {

tmp[k++] = array[s2++];

}

}

while (s1 <= e1){

tmp[k++] = array[s1++];

}

while (s2 <= e2){

tmp[k++] = array[s2++];

}

for (int i = 0; i < tmp.length; i++) {

array[i+low] = tmp[i];

}

}

public static void mergeSortInternal(int[] array,int low ,int high){

if(low >= high) return;

int mid = (low + high) / 2;

mergeSortInternal(array,low,mid);

mergeSortInternal(array,mid+1,high);

merge(array,low,high,mid);

}

public static void mergeSort(int[] array){

mergeSortInternal(array,0,array.length - 1);

}

7.4 代码实现—非递归

public static void merge1(int[] array,int gap){

int[] tmp = new int[array.length];

int k = 0;

int s1 = 0;

int e1 = s1 + gap - 1;

int s2 = e1 + 1;

int e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1;

while (s2 < array.length){

while (s1 <= e1 && s2 <= e2){

if(array[s1] <= array[s2]){

tmp[k++] = array[s1++];

}else {

tmp[k++] = array[s2++];

}

}

while (s1 <= e1){

tmp[k++] = array[s1++];

}

while (s2 <= e2){

tmp[k++] = array[s2++];

}

s1 = e2 + 1;

e1 = s1 + gap - 1;

s2 = e1 + 1;

e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1;

}

while (s1 <= array.length - 1){

tmp[k++] = array[s1++];

}

for (int i = 0; i < tmp.length; i++) {

array[i] = tmp[i];

}

}

public static void mergeSort1(int[] array){

for (int i = 1; i < array.length; i*=2) {

merge1(array,i);

}

}

7.5 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n * log(n))O(n * log(n))O(n * log(n))O(n)稳定

8.计数排序

当输入的元素是 n 个 0 到 k 之间的整数时，它的运http://行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

8.1 算法的步骤

（1）找出待排序的数组中最大和最小的元素（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

8.2 动图演示

8.3 代码实现

public static void CountingSort(int[] array){

int maxValue = GetMaxValue(array);

int bucketLen = maxValue + 1;

int[] bucket = new int[bucketLen];

for (int value:array) {

bucket[value]++;

}

int index = 0 ;

for (int i = 0; i < bucketLen; i++) {

while(bucket[i] > 0){

array[index++] = i;

bucket[i]--;

}

}

}

public static int GetMaxValue(int[] array){

int maxValue = array[0];

for (int i = 0; i < array.length; i++) {

if(maxValue < array[i]){

maxValue = array[i];

}

}

return maxValue;

}

8.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n+k)O(n+k)O(n+k)O(k)稳定

9.桶排序

9.1 原理

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

9.2 算法的步骤

设置一个定量的数组当作空桶；遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序；从不是空的桶里把排好序的数据拼接起来。

9.3 画图解析

9.4 代码实现

public static void bucketSort(int[] arr) {

if (arr.length == 0) {

return;

}

int minValue = arr[0];

int maxValue = arr[0];

for (int value : arr) {

if (value < minValue) {

minValue = value;

} else if (value > maxValue) {

maxValue = value;

}

}

//得到最大和最小元素

int bucketNum = (maxValue - minValue) / arr.length + 1;//桶的数量

ArrayList> bucket = new ArrayList<>(bucketNum);

for (int i = 0; i < bucketNum; i++) {

bucket.add(new ArrayList<>());

}

//将元素放入到桶中

for (int i = 0; i < arr.length; i++) {

int num = (arr[i] - minValue) / arr.length;

bucket.get(num).add(arr[i]);

}

for (int i = 0; i < bucket.size(); i++) {

//这里是比较,可以选择其他的方式实现,这里为了演示TLrDZeUrj采取Collection的sort

Collections.sort(bucket.get(i));

}

// 将桶中的元素赋值到原序列

int index = 0;

for(int i = 0; i < bucket.size(); i++){

for(int j = 0; j < bucket.get(i).size(); j++){

arr[index++] = bucket.get(i).get(j);

}

}

}

9.5 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n+k)O(n^2)O(n+k)O(n+k)稳定

10.基数排序

10.1 算法的步骤

取得数组中的最大数，并取得位数；arr为原始数组，从最低位开始取每个位组成radix数组；对radix进行计数排序（利用计数排序适用于小范围数的特点）

10.2 动图演示

10.3 代码实现

public static int getNumLength(int num){

if(num == 0) return 1;

int count = 0;

for (int i = num; i != 0; i /= 10) {

count++;

}

return count;

}

public static void RadixSort(int[] array){

int maxValue = array[0];

for (int i = 0; i < array.length; i++) {

if(maxValue < array[i]){

maxValue = array[i];

}

}

int maxDigit = getNumLength(maxValue);

int mod = 10;

int dev = 1;

for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {

int[][] counter = new int[mod * 2][0];

for (int j = 0; j < array.length; j++) {

int bucket = ((array[j] % mod) / dev) + mod;

counter[bucket] = arrayAppend(counter[bucket], array[j]);

}

int pos = 0;

for (int[] bucket : counter) {

for (int value : bucket) {

array[pos++] = value;

}

}

}

}

public static inTLrDZeUrjt[] arrayAppend(int[] arr, int value) {

arr = Arrays.copyOf(arr, arr.length + 1);

arr[arr.length - 1] = value;

return arr;

}

10.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n*k)O(n*2)O(n*k)O(n+k)稳定

总结：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。