冒泡排序
- 一共进行
arr.length-1次循环 - 每轮中两两比较，前者比后者大交换，将最大值排到末尾，不参与下一轮排序
- 如果发现在某轮排序中，没有发生一次交换， 可以提前结束冒泡排序
/**
* 冒泡排序
* @param arr
*/
private static void BubbleSort(int[] arr) {
//控制比较轮数,两两比较，需要arr.length-1轮
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = true;
//每轮中两两比较，前者比后者大交换
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j + 1] < arr[j]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
//一轮中都没有出现交换，退出
if (flag) {
break;
}
}
}
选择排序
在n个数中找到最小（大）的放到最前（后）面，再在剩下的n-1个数中找到最小的放到第二个位置，以此类推，直到数组中只剩下一个元素。
/**
* 选择排序
* @param arr
*/
private static void selectSort(int[] arr) {
//控制比较轮数,两两比较，需要arr.length-1轮
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
//记录最小值索引
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
//与当前轮首位交换
if (i != min) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
插入排序
把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
/**
* 插入排序
* @param arr
*/
private static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
//待插入的数
int insertVal = arr[i];
//待插入索引
int insertIndex = i - 1;
// 给insertVal 找到插入的位置
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
// 当退出while循环时，说明插入的位置找到, insertIndex + 1
if (insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
}
}
希尔排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
/**
* 希尔排序
* @param arr
*/
private static void shellSort(int[] arr) {
// 增量gap, 并逐步的缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//gap版插入排序
for (int i = gap; i < arr.length; i++) {
int insertVal = arr[i];
int insertIndex = i - gap;
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + gap] = arr[insertIndex];
insertIndex -= gap;
}
if (i != insertIndex) {
arr[insertIndex + gap] = insertVal;
}
}
}
}
快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
/**
* 快速排序
* @param arr
* @param low
* @param high
*/
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = getPivot(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
/**
* 枢轴
* @param arr
* @param low
* @param high
* @return
*/
private static int getPivot(int[] arr, int low, int high) {
int pivot = arr[low];
while (low < high) {
//如果枢轴定义为低位端，从高位端先遍历
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
//此时low=high,即为枢轴
arr[low] = pivot;
return low;
}
归并排序
采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
/**
* 递归拆分+合并
* @param arr
* @param start
* @param end
* @param temp
*/
private static void mergeSort(int[] arr, int start, int end, int[] temp) {
if (start < end) {
//中间索引
int mid = (start + end) / 2;
//向左递归分解
mergeSort(arr, start, mid, temp);
//向右递归分解
mergeSort(arr, mid + 1, end, temp);
//退栈合并
merge(arr, start, end, temp);
}
}
/**
* 合并
* @param arr
* @param start
* @param end
* @param temp
*/
private static void merge(int[] arr, int start, int end, int[] temp) {
int mid = (start + end) / 2;
int left = start;
int right = mid + 1;
int cur = 0;
//左右比较，有序添加到temp数组
while (left <= mid && right <= end) {
temp[cur++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
}
//添加剩余数据
while (left <= mid) {
temp[cur++] = arr[left++];
}
while (right <= end) {
temp[cur++] = arr[right++];
}
//temp数组复制到原数组
left = start;
cur = 0;
while (left <= end) {
arr[left++] = temp[cur++];
}
}
基数排序
- 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。
- 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
- 基数排序(Radix Sort)是桶排序的扩展
- 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
/**
* 基数排序
* @param arr
*/
private static void radixSort(int[] arr) {
//查找最大数
int max = arr[0];
for (int i : arr) {
max = max > i ? max : i;
}
//得到最大位数
int maxLength = (max + "").length();
//定义二维桶数组
int[][] bucket = new int[10][arr.length];
//定义数组保存每个桶中的元素个数
int[] bucketECount = new int[10];
//放入桶
for (int i = 0; i < maxLength; i++) {
for (int j = 0; j < arr.length; j++) {
//取出对应位的值，按个十百...的顺序
int digit = (int) (arr[j] / Math.pow(10, i) % 10);
bucket[digit][bucketECount[digit]++] = arr[j];
}
}
//取出
int index = 0;
for (int i = 0; i < bucket.length; i++) {
if (bucketECount[i] != 0) {
for (int j = 0; j < bucketECount[i]; j++) {
arr[index++] = bucket[i][j];
}
}
bucketECount[i] = 0;
}
}
常用排序算法总结和对比
转载：https://blog.csdn.net/Chill_Lyn/article/details/104630292
查看评论