Java常用的八种排序算法：
插入排序 – 直接插入排序
每次将待排序的记录按照关键字的大小，插入到前面已经排好序的记录的适当位置。直到全部记录插入完成。
代码实现
/**
* 直接插入排序 O(n^2) 由于插入排序需要交换数据的次数多影响性能，插入排序时寻找合适的插入位置
* 数组越有序，插入排序效率越高，对于完全有序的数组 O(n)
* @param arr
* @return
*/
public static int[] insertionSort(int[] arr) {
int n = arr.length;
int insertNum;
for (int i = 1; i < n; i++) {
insertNum = arr[i];// 要插入的数
int j = i-1;
while (j >= 0 && arr[j] > insertNum) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = insertNum;
}
return arr;
}
插入排序 – 希尔排序
又称最小增量排序，在时间效率上比直接插入排序有较大的改进。
先取定一个小于n的整数d1作为第一个增量，把全部记录分成d1个组，所有的距离为d1的倍数的记录放在同一个组，在各组中进行插入排序；
然后取第二个增量d2<d1，重复上述分组和排序，知道d1=1,所有记录都放在一组中进行直接插入排序为止。
代码实现
/**
* 希尔排序
* 分组进行直接插入排序
* @param arr
*/
public void shellSort(int[] arr) {
int d = arr.length;
while (d != 0) {
d = d / 2;
for (int x = 0; x < d; x++) {
for (int i = x + d; i < arr.length; i += d) {
int insertNum = arr[i];// 要插入的元素，为序列的第二位数
int j = i - d; // 序列的第一位数的坐标
while (j >= 0 && insertNum < arr[j]) {
arr[j + 1] = arr[j];
j -= d;
}
arr[j + d] = insertNum;
}
}
}
}
如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序
选择排序 – 简单选择排序
/**
* 简单选择排序 O(n^2)
* 从一个元素开始，遍历后边的元素找出后面最小的元素与之交换
*
* @param arr
*/
public static void selectedSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
// 寻找 [i,n) 区间里的最小值
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
选择排序 – 堆排序
public void heapSort(int[] arr) {
int size = arr.length;
for (int i = 0; i < size - 1; i++) {
buildMaxHeap(arr, size - 1 - i);
// 交换堆顶和最后一个元素
swap(arr, 0, size - 1 - i);
}
} public void buildMaxHeap(int[] data, int lastIndex) {
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
int k = i;
while (k * 2 + 1 <= lastIndex) {
int biggerIndex = 2 * k + 1;
if (biggerIndex < lastIndex && data[biggerIndex] < data[biggerIndex + 1]) {
biggerIndex++;
}
if (data[k] > data[biggerIndex])
break;
swap(data, k, biggerIndex);
k = biggerIndex;
}
}
} public void swap(int[] data, int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
交换排序 – 冒泡排序
将序列中所有元素两两比较，将最大的放在最后面。
代码实现
/**
* 冒泡排序
* @param arr
* @return
*/
public static void Bubble(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
if (arr[j] > arr[j++]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
交换排序 – 快速排序
选择第一个数为p，小于p的数放在左边，大于p的数放在右边。递归的将p左边和右边的数都按照第一步进行，直到不能递归。
要求时间最快时。
代码实现
/**
* 快速排序，是对冒泡排序的优化
*
* @param arr
*/
public void quickSort(int[] arr) { int n = arr.length;
quickSort(arr, 0, n - 1);
} private void quickSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int p = partition(arr, l, r);
quickSort(arr, l, l + p);
quickSort(arr, 1 + p + 1, r);
} /**
* 返回p ,使得arr[l,p-1] < arr[p] arr[p]=<arr[p+1,r]
*
* @param arr
* @param l
* @param r
* @return
*/
private int partition(int[] arr, int l, int r) { int v = arr[l];
int j = l; for (int i = l + 1; i <= r; i++) {
if (arr[i] < v) {
swap(arr, ++j, i);
}
}
swap(arr, l, j);
return j;
} /**
* 返回p ,使得arr[l,p-1] <= arr[p] arr[p]<=arr[p+1,r],当有重复数据时效率更高
*
* @param arr
* @param l
* @param r
* @return
*/
private int partition2(int[] arr, int l, int r) {
int v = arr[l];
int i = l + 1, j = r;
while (true) {
while (i <= r && arr[i] < v)
i++;
while (j >= l + 1 && arr[j] > v)
j--;
if (i > j) {
break;
}
swap(arr, i, j);
i++;
j--;
}
return j;
}
归并排序
速度仅次于快排，内存少的时候使用，可以进行并行计算的时候使用。
选择相邻两个数组成一个有序序列。
选择相邻的两个有序序列组成一个有序序列。
重复第二步，直到全部组成一个有序序列。
/**
* 归并算法 O(nlogn) 比插入算法 选择算法节省时间，但是时间复杂度会增加
* @param arr
*/
public void mergeSort(int[] arr) {
int n = arr.length;
mergeSort(arr, 0, n - 1);
} private void mergeSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
if (arr[mid] > arr[mid + 1]) {
MergeAll(arr, l, r, mid);
}
} /**
* 将排序好后的两个数组进行排序
* @param arr
* @param l
* @param r
* @param mid
*/
private void MergeAll(int[] arr, int l, int r, int mid) { // 给要排序的数组赋值 [l,r]
int[] copyArr = new int[r - l + 1];
for (int k = 0; k < copyArr.length; k++) {
copyArr[k] = arr[l + k];
} int i = l;
int j = mid + 1; for (int k = l; k <= r; k++) {
if (j > r) {
arr[k] = copyArr[i - l];
i++;
} else if (i > mid) {
arr[k] = copyArr[j - l];
j++;
} else if (copyArr[i - l] < copyArr[j - l]) {
arr[k] = copyArr[i - l];
i++;
} else if (copyArr[i - l] >= copyArr[j - l]) {
arr[k] = copyArr[j - l];
j++;
}
}
}
基数排序
用于大量数，很长的数进行排序时。
将所有的数的个位数取出，按照个位数进行排序，构成一个序列。
将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。
public void sort(int[] array) {
// 首先确定排序的趟数;
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
int time = 0;
// 判断位数;
while (max > 0) {
max /= 10;
time++;
}
// 建立10个队列;
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> queue1 = new ArrayList<Integer>();
queue.add(queue1);
}
// 进行time次分配和收集;
for (int i = 0; i < time; i++) {
// 分配数组元素;
for (int j = 0; j < array.length; j++) {
// 得到数字的第time+1位数;
int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> queue2 = queue.get(x);
queue2.add(array[j]);
queue.set(x, queue2);
}
int count = 0;// 元素计数器;
// 收集队列元素;
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
ArrayList<Integer> queue3 = queue.get(k);
array[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
