冒泡排序
算法步骤
- 比较相邻元素，如果第一个比第二个大，就交换它们 最后的元素就是最大的
- 重复以上步骤，除了最后一个
参考代码
public static void bubbleSort(int[] values) {
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < values.length - 1 - i; j++) {
//减i原因：内层循环，每循环完一趟就在数组末产生一个最大数，即最大数就不用比较了。
if (values[j] > values[j + 1]) {
int temp = values[j];
values[j] = values[j + 1];
values[j + 1] = temp;
}
}
}
}
选择排序
算法步骤
-
找到最小元素 放到起始位置
-
重复找到所有的元素
参考代码
public static void selectSort(int[] arr) {
// 总共要经过 N-1 轮比较
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
// 每轮需要比较的次数 N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 记录目前能找到的最小值元素的下标
min = j;
}
}
// 将找到的最小值和i位置所在的值进行交换
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
}
插入排序
只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤
- 将第一个元素看作是一个有序序列，把第二个元素到左后一个元素当成为未排序序列
- 从头到尾扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置
参考代码
public static void insertSort(int[] arr) {
// 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for (int i = 1; i < arr.length; i++) {
// 记录要插入的数据
int tmp = arr[i];
// 从已经排序的序列最右边的开始比较，找到比其小的数
int j = i;
while (j > 0 && tmp < arr[j - 1]) { //插入的数据小于 一直循环 值向前移动一位
arr[j] = arr[j - 1];
j--;
}
arr[j] = tmp;
}
}
希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
针对选择排序固定的比较次数，我们使用了往局部有序数组里插入数据的插入排序。
如果整个队伍原本是大致有序的，最后再来插入排序效率会很快。
但是开始排序时，距离它正确的位置很远时，效率很低
通过大步伐让队伍大致一致
int gap = 1;
while (gap < arr.length) {
gap = gap * 3 + 1;
}
while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
gap = (int) Math.floor(gap / 3);
}
归并排序
如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。 （分而治之的思想）
public static void mergeSort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
public static void sort(int[] arr, int left, int right) {
// 递归终止条件
if(left >= right) {
return;
}
// 获取 left right 之间的中间位置
int mid = left + ((right - left) >> 1);
// 分治递归
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
// 合并数据
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
// 比较左右两部分的元素，哪个小，把那个元素填入temp中
while(p1 <= mid && p2 <= right) {
temp[i++] = arr[p1] < = arr[p2] ? arr[p1++] : arr[p2++];
}
// 上面的循环退出后，把剩余的元素依次填入到temp中
// 以下两个while只有一个会执行
while(p1 <= mid) {
temp[i++] = arr[p1++];
}
while(p2 <= right) {
temp[i++] = arr[p2++];
}
// 把最终的排序的结果复制给原数组
for(i = 0; i < temp.length; i++) {
arr[left + i] = temp[i];
}
}
快速排序
1.对于未排序序列，从中选取一个基准值k,将小于k的放到左边，大于k的放到右边
2.接着以k为中间，左右两边的分割作为新的序列，重复1的操作
public int[] quickSort(int[] arr) {
return quick(arr, 0, arr.length - 1);
}
private int[] quick(int[] arr, int left, int right) {
if (left < right) { //left right一直变化 直到left <right递归结束
int partitionIndex = partition(arr, left, right);
quick(arr, left, partitionIndex - 1);
quick(arr, partitionIndex + 1, right);
}
return arr;
}
private int partition(int[] a, int low, int high) {
//取每个序列的第一个值作为基准值
int pivotkey = a[low];
while (low < high) {
//从序列的右边开始往左遍历，直到找到小于基准值的元素
while (high > low && a[high] >= pivotkey) {
high--;
}
//将元素直接赋予给左边第一个，即pivotkey所在的位置
a[low] = a[high];
//从序列的左边边开始往右遍历，直到找到大于基准值的元素
while (high > low && a[low] <= pivotkey) {
low++;
}
//此时的a[high]<pivotkey,已经被赋予到左边，所以可以将元素赋予给a[high]
a[high] = a[low];
}
//最后的low是基准值所在的位置
a[low] = pivotkey;
return low;
}
堆排序
什么是堆
1.完全二叉树（除了最后一层，其上各一层，结点数达到最大值）
2.父结点大于等于子节点 （大根堆） 父结点小于等于子节点 （小根堆）
满足的条件
parent = (i - 1 )/2;
c1 = 2i + 1;
c2 = 2i + 2;
代码
/**
* heapify
*
* @param tree tree
* @param n 有几个结点
* @param i 从第几个做headify
*/
void heapify(int tree[], int n, int i) // 从第 i 个 开始做 heapify
{
if (i >= n) {
return;
}
int c1 = 2 * i + 1;
int c2 = 2 * i + 2;
int max = i;
if (c1 < n && tree[c1] > tree[max]) {
max = c1;
}
if (c2 < n && tree[c2] > tree[max]) {
max = c2;
}
if (max != i) {
swap(tree, max, i);
heapify(tree, n, max);
}
}
/**
* 构建堆
* @param tree
* @param n
*/
void build_heap(int tree[], int n) {
int last_node = n - 1;
int parent = (last_node - 1) / 2;
for (int i = parent; i >= 0; i--) {
heapify(tree, n, i);
}
}
/**
* 堆排序
* @param tree
* @param n
*/
void heap_sort(int tree[], int n) {
//数组堆化
build_heap(tree, n);
//截取最大值
for (int i = n - 1; i >= 0; i--) {
swap(tree, i, 0);
heapify(tree, i, 0);
}
}
void swap(int a[], int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
计数排序
算法思想
量大但是范围小
- 某大型企业员工数万名员工年龄排序
- 如何快速得知高考名次
复杂度
空间复杂度： n+k(k 计数数组长度) 时间复杂度： n+k 遍历原数组 ，计数数组，目标数组
public static int[] countSort(int[] arr, int countLen) {
int[] result = new int[arr.length];
int[] count = new int[countLen + 1];
for (int i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
for (int i = 0, j = 0; i < count.length; i++) {
while (count[i]-- > 0) {
result[j++] = i;
}
}
return result;
}
public static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
桶排序
算法步骤
- 找到最大值最小值，计算出范围
- 设置固定大小的桶
- 对每个不为空的桶进行排序
- 拼接不为空的桶中数据，得到结果
复杂度分析
代码
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函数将数据分配到各个桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 对每个桶进行排序，这里使用了插入排序
bucket = insertSort.sort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
/**
* 自动扩容，并保存数据
*
* @param arr
* @param value
* @return
*/
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
基数排序
基数排序算法就是将整数或字符串切分成不同的数字或字符，然后按对应位置的数或字符分别进行比较。
非 排序 桶思想的一种 多关键字排序
算法步骤
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
- 从最低位开始，依次进行一次排序
- 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
public static int[] radixSort(int[] arr) {
int maxValue = getMaxValue(arr);
int numLength = getNumLenght(maxValue);
int[] result = new int[arr.length];
for (int i = 0; i < numLength; i++) {
int[] count = new int[10];
int division = (int) Math.pow(10, i);
// 统计每个整数出现的次数
for (int j = 0; j < arr.length; j++) {
int num = arr[j] / division % 10;
count[num]++;
}
// 累加次数 算出在result的位置
for (int m = 1; m < count.length; m++) {
count[m] += count[m - 1];
}
//从后向前遍历元素，将她放在有序数组中的合适位置
for (int n = arr.length - 1; n >= 0; n--) {
//count数组中索引值的位置
int num = arr[n] / division % 10;
result[--count[num]] = arr[n];
}
//复制结果到arr数组中 空间重复利用
System.arraycopy(result,0,arr,0,arr.length);
}
return result;
}
public static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
/**
* 获取最高位数
*/
protected static int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
复杂度分析
