常见排序算法

简单整理常用算法，记录在此。

?

package com.demo.sort;

import java.util.Arrays;

public class Sort {
public static void main(String[] args) {

int size = 10;
int[] arr = new int[size];
for (int j = 0; j < size; j++) {
for (int i = 0; i < size; i++) {
arr[i] = (int) (100*size*Math.random() +1);
}
//测试冒泡
// System.out.println(Arrays.toString(bubble(arr)));
//测试选择
// System.out.println(Arrays.toString(select(arr)));
//测试快速
// System.out.println(Arrays.toString(fast(arr,5)));
//测试插入排序
// System.out.println(Arrays.toString(insert(arr)));
//测试希尔排序
// System.out.println(Arrays.toString(shell(arr)));
//测试桶排序
// System.out.println(Arrays.toString(bucket(arr)));
//测试基数排序
// System.out.println(Arrays.toString(radix(arr)));
//测试归并排序
// mergeSort(arr);
// System.out.println(Arrays.toString(arr));
//测试堆排序
// System.out.println(Arrays.toString(heap(arr)));
}

}

/**
* heap sort 堆排序原理（升序）：
* 将序列抽象为二叉树，构建最大堆；
* 依次将最大元素与待排序列的最后位置交换；
* 遍历刷新直至最后一个元素；
* 算法思想：完全二叉树
* 时间复杂度：O[NlogN]
* 空间复杂度：O[1]
* 稳定性：不稳定
*/
private static int[] heap(int[] arr) {

for (int i = 0; i < arr.length; i++) {
maxHeap(arr,arr.length - i);
// 交换
int temp = arr[0];
arr[0] = arr[(arr.length - 1) - i];
arr[(arr.length - 1) - i] = temp;
}
return arr;
}

private static void maxHeap(int[] arr,int size) {
for (int i = size - 1; i >= 0; i--) {
buildheap(arr,i,size);
}
}

private static void buildheap(int[] arr,int rootNode,int size) {
if (rootNode < size) {

int leftNode = 2 * rootNode + 1;
int rightNode = 2 * rootNode + 2;
int max = rootNode;

if (leftNode < size) {
if (arr[leftNode] > arr[max]) {
max = leftNode;
}
}

if (rightNode < size) {
if (arr[rightNode] > arr[max]) {
max = rightNode;
}
}

if (max != rootNode) {
int tmp = arr[max];
arr[max] = arr[rootNode];
arr[rootNode] = tmp;

buildheap(arr,max,size);
}

}
}

/**merge sort 归并排序原理（升序）：
* 把序列看做对两个有序队列的排序，递归对两个序列排序直至队列只包含两个元素，然后将两个有序队列合并；
* 算法思想：递归加分治
* 时间复杂度：O[NlogN]
* 空间复杂度：O[N]
* 稳定性：稳定
*/
public static void mergeSort(int[] array) {

int length = array.length;
int middle = length / 2;

if (length > 1) {
int[] left = Arrays.copyOfRange(array,middle);// 拷贝数组array的左半部分
int[] right = Arrays.copyOfRange(array,middle,length);// 拷贝数组array的右半部分
mergeSort(left);// 递归array的左半部分
mergeSort(right);// 递归array的右半部分
merge(array,left,right);// 数组左半部分、右半部分合并到Array
}
}

// 合并数
private static void merge(int[] result,int[] left,int[] right) {

int i = 0,l = 0,r = 0;

while (l < left.length && r < right.length) {
if (left[l] < right[r]) {
result[i] = left[l];
i++;
l++;
} else {
result[i] = right[r];
i++;
r++;
}
}

while (r < right.length) {// 如果右边剩下合并右边的
result[i] = right[r];
r++;
i++;
}

while (l < left.length) {
result[i] = left[l];
l++;
i++;
}
}

/**
* radix sort 基数排序原理（升序）：
* 桶排序的改进版窗，桶的大小固定为10；
* 首先对数组元素的个位数值大小按桶排序进行排序；接着按元素的十位数值大小按桶排序进行排序；依次按桶排序将最高位排序完成；
* 时间复杂度：O[d(r+N)]
* 空间复杂度：O[rd+N]
* 稳定性：稳定
*/
private static int[] radix(int[] arr) {
if (null == arr || arr.length == 0) {
return null;
}
int[] tmp1 = new int[10];
int[][] tmp2 = new int[10][arr.length];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
int num = 1;
while ((max /= 10) > 0) {
num += 1;
}
for (int i = 0; i < num; i++) {
for (int j = 0; j < arr.length; j++) {
int index = arr[j] / ((int) Math.pow(10,i)) % 10;
tmp2[index][tmp1[index]] = arr[j];
tmp1[index] += 1;
}
int k = 0;
for (int j = 0; j < tmp1.length; j++) {
// while(tmp1[j] != 0){
for (int h = 0; h < tmp1[j]; h++) {
arr[k] = tmp2[j][h];
// tmp2[j][h] = 0;
// tmp1[j]--;
k++;
}
tmp1[j] = 0;
// }
}
}

return arr;
}

/**
* bucket sort 桶排序原理（升序）：
* 找出序列最大值，创建最大值加一的新数组；
* 遍历数组，元素值对应新数组下标的位置加一；
* 遍历新数组，将元素值非0的下标值载入原数组；
* 时间复杂度：O[N]
* 空间复杂度：O[N]
* 稳定性：不稳定
*/
private static int[] bucket(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
int[] tmp = new int[max + 1];
for (int j = 0; j < arr.length; j++) {
tmp[arr[j]] += 1;
}

int k = 0;
for (int i = 0; i < tmp.length; i++) {
while (tmp[i] != 0) {
arr[k] = i;
k++;
tmp[i]--;
}
}
return arr;
}

/**
* shell sort 希尔排序原理（升序）：
* 插入排序改进版；
* 把元素分组，每组插入排序 ；
* 改变分组增量，直至增量为1；
* 时间复杂度：O[N^2]
* 空间复杂度：O[1]
* 稳定性：不稳定
*/
private static int[] shell(int[] arr) {
int len = arr.length;
for (int i = len / 2; i > 0; i = i / 2) {// 增量
for (int j = 0; j < i; j++) {// 分组数
for (int k = 1; k < len / i; k++) {// 每组的元素数
int m = k - 1;
for (; m >= 0; m--)
// 逆序，前面部分为有序
if (arr[j + i * k] >= arr[j + i * m])
break;

if (m != k - 1) {
int n = k;
int tmp = arr[j + i * n];
for (; n > m + 1; n--) {
arr[j + i * n] = arr[j + i * (n - 1)];
}

arr[j + i * n] = tmp;
}
}
}
}
return arr;
}

/*
* insert sort 插入排序原理（升序）：
* 改原理是将待排序元素插入一个有序队列，将左边部分当做一个有序队列；
* 时间复杂度：O[N^2]
* 空间复杂度：O[1]
* 稳定性：稳定
*/
private static int[] insert(int[] arr) {

for (int i = 1; i < arr.length; ++i) {
/*
* 分为1,2两部分处理，可以囊括j = beg - 1时的情况 即需要将arr[i]插入到首元素前的位置，若使用一个for
* 包括这两部分，则会在发生这种情况时退出
*/
/* 1 */
int j = i - 1;
for (; j >= 0; --j)
if (arr[j] <= arr[i])
break;
/* 2 */
if (j != i - 1) {
int temp = arr[i];
for (int k = i; k > j + 1; --k) {
arr[k] = arr[k - 1];
}
arr[j + 1] = temp;
}
}
return arr;
}

/*
* fast sort 快速排序原理（升序）：
* 选一基准元素，小于其大小的元素放在左边，大于它的元素放在右边；
* 取基准元素的前后两部分做同样处理，直至基准元素的两边各有一个元素为止；
* 时间复杂度：O[NlogN]
* 空间复杂度：O[NlogN]
* 稳定性：不稳定
*/
private static int[] fast(int[] arr,int begin,int end) {
if (begin >= end) {
return arr;
}
int lindex = begin;
int rindex = end;
int mid = arr[lindex];
while (lindex < rindex) {
while (lindex < rindex) {
if (arr[rindex] < mid) {
arr[lindex++] = arr[rindex];
break;
}
--rindex;
}

while (lindex < rindex) {
if (arr[lindex] >= mid) {
arr[rindex--] = arr[lindex];
break;
}
++lindex;
}
}
arr[lindex] = mid;
fast(arr,begin,lindex);
fast(arr,rindex + 1,end);
return arr;
}

/*
* select sort 选择排序原理（升序）：
* 找出元素最小值放在第一位，接着次小值放在第二位，依次将数组升序排列
* 时间复杂度：O[N^2]
* 空间复杂度：O[1]
* 稳定性：不稳定
*/
private static int[] select(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[i]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
return arr;
}

/* * bubble sort 冒泡排序原理（升序）： * 依次比较相邻两个元素，若后位元素较大则交换至，直至最后一位元素为最大值； * 接着进行下一轮比较，直至倒数第二位元素为次大值； * 进行比较至所有元素为升序排列 * 时间复杂度：O[N^2] * 空间复杂度：O[1] * 稳定性：不稳定 */ private static int[] bubble(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } return arr; }}