菜鸟笔记十大排序算法
十大排序算法分别为：冒泡排序、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、桶排序、计数排序、基数排序
他们的时间复杂度分别为：
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
- n：数据规模
- k："桶"的个数
- In-place：占用常数内存，不占用额外内存
- Out-place：占用额外内存
- 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
冒泡排序
冒泡排序是基于交换排序的典型， 是快速排序思想的基础，是一种稳定的排序算法。它的时间复杂度为O(n2)
思路：循环遍历多次每次从前往后把大元素往后调，每次确定一个最大(最小)元素，多次后达到排序序列。(或者从后向前把小元素往前调)。
实现方式：
public static void bubble(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
boolean flag = true;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
arr[j] = arr[j] + arr[j + 1];
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
flag = false;
}
}
if (flag) {
break;
}
}
}
快速排序
快速排序是对冒泡排序的一种改进，采用递归分治的方法进行求解。而快排相比冒泡是一种不稳定排序,时间复杂度最坏是O(n2),平均时间复杂度为O(n log n),最好情况的时间复杂度为O(n log n)。
对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
思路：
-
从数列中挑出一个元素，称为 “基准”（pivot）;
-
分区：将比这个数大或等于的数放在它的右边，小于它的数放在它的左边
-
再对左右区间重复第二步，直到各区间只有一个数
具体步骤：选择一个基准数，这个基准数的位置记为第一个坑 从后往前寻找比他小的数字，找到的第一个比他小的数字则挖走填入到前一个坑中，此时挖走数据，则形成了一个新的坑，然后从前往后找比他大的数，找到的第一个也填到上一个挖走数字的坑中。以此类推，直到无法再查询。
注意：每找到一个数，就换一个方向，并且把这个数字填到上一次挖出的坑中
实现方法：
class QuickSort {
public void quickSort(int[] arr, int start, int end) {
// 找出分左右两区的位置索引位置，然后对左右两区进行递归调用
if (start < end) {
int index = getIndex(arr, start, end);
// 对左区递归
quickSort(arr, start, index - 1);
// 对右区递归
quickSort(arr, index + 1, end);
}
}
private static int getIndex(int[] arr, int start, int end) {
int i = start;
int j = end;
int x = arr[i];
while (i < j) {
// 从后往前找，如果找出来的数比基准数大，则让 j--
while (i < j && arr[j] >= x) {
j--;
// 当 j<i 或者 arr[j]<x 则跳出循环
// 跳出循环如果 i<j ，则说明找到了比基准数小的数
}
if (i < j) {
// 将这个数字填入到上一个坑
arr[i] = arr[j];
// 由于上一个坑已经被填入，所以需要 i++
i++;
}
// 从前往后找比基准数小的数字
while (i < j && arr[i] < x) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
// 此时 i 和 j相等，arr[i]与arr[j]都是一样的
// 把基准数放到最后一个坑
arr[i] = x;
// 返回索引位置
return i;
}
}
插入排序
插入排序是一种最简单的排序方法，他是将一个数据插入到一个长度为m的有序表中，并且让他保持有序性
从1索引处开始，将后面的元素插入到之前的有序列表中，并且使之保持有序。
class FastSort {
// 外层循环定义轮次
public void fastSort(int[] arr) {
// 因为是从1索引处开始插入，所以这里 i 要从1开始
for (int i = 1; i < arr.length; i++) {
// 里层循环进行比较插入
int j = i;
while (j > 0 && arr[j] < arr[j - 1]) {
arr[j] = arr[j] + arr[j - 1];
arr[j - 1] = arr[j] - arr[j - 1];
arr[j] = arr[j] - arr[j - 1];
j--;
}
}
}
}
// 或者
class FastSort {
// 外层循环定义轮次
public void fastSort(int[] arr) {
// 因为是从1索引处开始插入，所以这里 i 要从1开始
for (int i = 1; i < arr.length; i++) {
// 里层循环进行比较插入
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
arr[j] = arr[j] + arr[j - 1];
arr[j - 1] = arr[j] - arr[j - 1];
arr[j] = arr[j] - arr[j - 1];
}
}
}
}
}
希尔排序
希尔排序又称缩小增量排序，他是对插入排序的一个优化。直接插入排序实际上就是增量为1的希尔排序。
思路：先将原数组按照增量（ht）分组，每个子序列按照直接插入法排序。排好之后用下一个增量 ht/2 再将数组分为子序列，再使用直接插入法排序，直到 增量为1的时候，整个序列排序完成。经过第一轮排序，会让数组大致有序，再进行细致的排序
希尔排序的关键在于怎样选择一个合适的增量，第一次排序可以设置增量为数组长度的一半
d就是增量，每间隔为5的两个元素组成一组，每一趟排序，将每组元素中小的元素放前面，大的元素放后面（前者大则两者位置互换，前者小则不做操作）
实现方法
// 设置增量为数组一半时的方法
class shellSort {
public void shellSort(int[] arr) {
// 定义ht为首次排序的增量，长度为数组的一半
for (int ht = arr.length / 2; ht > 0; ht /= 2) {
for (int i = ht; i < arr.length; i++) {
for (int j = i; j > ht - 1; j -= ht) {
if (arr[j] < arr[j - ht]) {
swap(arr, j, j - ht);
}
}
}
}
}
public void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
有的时候，增量设置为数组长度的一半也不是很好，这时我们就可以使用克努特序列
克努特序列（ Knuth 序列 ）：数组从1 开始，通过递归表达式 h = h*3 + 1 来产生。倒推公式则为h = ( h - 1 ) / 3
优化后的算法：
class ShellSort {
public void shellSort(int[] arr) {
// 通过克努特序列来确定增量
int ht = 1;
// 注意此处要让数组长度除以3
while (ht <= arr.length / 3) {
// 克努特序列思想
ht = ht * 3 + 1;
}
// 缩小增量则是反向的克努特序列式子
for (int h = ht; h > 0; h = (h - 1) / 3) {
for (int i = h; i < arr.length; i++) {
for (int j = i; j > h - 1; j -= h) {
if (arr[j] < arr[j - h]) {
swap(arr, j, j - h);
}
}
}
}
}
public void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
选择排序
思路：从0索引处开始，依次和后面的元素进行比较 ，小的元素往前放，经过一轮比较后，最小的元素就放在了最小索引处，每经过一轮比较，索引位置 + 1。
注意：换完位置之后，比较不停止，而是使用交换了位置的元素继续比较，直到比较到最后一个
例如：13 69 80 57 24 。假设此时进行第二轮比较，即从69开始
69比57大，则互换位置，注意此时：继续用索引为1 位置的数字进行比较，即用57继续往后比较，57比24大，互换位置。
也就是说，比较只有到达数组末尾才会结束，互换位置之后继续用当前索引位置的数字进行比较。数组长度为N，则要比较 N-1 轮，
实现方法：
class ChooseSort {
public void chooseSort(int[] arr) {
// 第一轮比较，从0索引处开始比较，只要比较 length - 1 轮
// 每比较完一轮，index++
for (int index = 0; index < arr.length - 1; index++) {
// 直接与索引处下一个数字进行比较，所以 i = index + 1
for (int i = 1 + index; i < arr.length; i++) {
if (arr[index] > arr[i]) {
swap(arr, index, i);
}
}
}
}
public void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序
思路：
- 将需要排序的序列构造成一个大顶堆（大根堆），此时，整个序列的最大值就是堆顶的根节点
- 将其与末尾元素进行交换，此时末尾就为最大值
- 然后将剩余 n-1 个元素重新构造成一个堆，这样会得到这 n 个元素的最小值
- 反复执行，直到有序
建立大顶堆时，是从最后一个非子叶节点开始从下往上调整的。
大顶堆结构的特点：每一个节点的值都大于或等于他左右孩子节点的值
如果数组长度为N，那么最后一个非子叶节点的位置就为 N/2 - 1。
在构建大顶堆的时候，因为最后要将最大的元素与当前轮的末尾元素进行交换，交换之后很可能剩下的元素就不满足大顶堆结构了，所以要递归调用构造大顶堆的方法，直到全部形成大顶堆结构。
每一轮构造大顶堆结构完成，最大元素放到末尾，下一轮的构造，这个元素就不参与了。所以下一轮的末尾元素位置为参与了构造大顶堆结构的数据位置。
详细理解：假设数组为 7，3，8，5，1，2，他的原始结构为
经过第一轮的构建，以及数字的交换，变成如下结构
此时，8为已经换到末尾的元素，那么下一轮他就不参与构建，所以下一轮的末尾元素就位置就变成了 1 所处的位置
关于堆排序的详细参考
数组可以看作是一个完全二叉树，数组从逻辑上来说就是一个堆结构
相让数组升序则使用大顶堆，相让数组降序则使用小顶堆。
用公式描述堆的定义
-
大顶堆：
arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]; -
小顶堆：
arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2];
实现方法：
public class testb {
public static void main(String[] args) {
MaxHeapSort maxHeapSort = new MaxHeapSort();
int arr[] = {
1, 0, 6, 7, 2, 3, 4, 53, 76, 1, 35, 23, -6, -32, -2, 45};
// 调用方法把数组调成大顶堆
maxHeapSort.firstConstructHeap(arr);
System.out.println(Arrays.toString(arr));
// 经过以上操作，数组已经变成大顶堆，此时把根元素与最后一个元素进行交换
maxHeapSort.changeValue(arr);
System.out.println(Arrays.toString(arr));
}
}
class MaxHeapSort {
// 第一次构建大顶堆的方法
public void firstConstructHeap(int[] arr) {
// 定义开始调整的位置(通过公式来设定)，位置为最后一个非叶子节点
int startIndex = arr.length / 2 - 1;
// 循环开始调整位置，下一个非叶子节点就是 当前坐标 - 1
for (int i = startIndex; i >= 0; i--) {
maxHeapSort(arr, arr.length, i);
}
}
public void changeValue(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
// 进行调换
swap(arr, 0, i);
// 调换完之后，把剩余元素调换为大顶堆
// 要重新获取左右节点，所以index传入0
maxHeapSort(arr, i, 0);
}
}
/**
* @param arr 要进行排序的数组
* @param size 需要调整的元素个数
* @param index 从哪里开始调整
*/
// 构建大顶堆
public void maxHeapSort(int[] arr, int size, int index) {
// 先获取左右子节点的索引，由堆的公式定义获得
int leftNodeIndex = index * 2 + 1;
int rightNodeIndex = index * 2 + 2;
// 查找最大节点对应的索引，先让他等于开始索引位置，再进行比较
int maxNodeIndex = index;
// 如果左节点的数字大于它，则互换索引
// 由于有递归调用，索引为不断增加，添加条件防止下标越界
if (leftNodeIndex < size && arr[leftNodeIndex] > arr[maxNodeIndex]) {
maxNodeIndex = leftNodeIndex;
}
if (rightNodeIndex < size && arr[rightNodeIndex] > arr[maxNodeIndex]) {
maxNodeIndex = rightNodeIndex;
}
// 如果最大索引位置不等于原来的位置，说明有比他大的数字
// 此时将最大数字移动到顶端
if (maxNodeIndex != index) {
swap(arr, maxNodeIndex, index);
// 换完位置后，可能下面的子树就不满足大顶堆结构了，所以要递归调用
maxHeapSort(arr, size, maxNodeIndex);
}
}
public void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
归并排序
归并排序的原理：假设初始序列有N个记录，则可以看成是N个有序的子序列，每个子序列的长度为1，然后两两归并，得到 N/2 个长度为2或1的有序子序列，再两两归并，重复步骤直到得到一个长度为N的有序序列为止。这种排序方法称为二路归并排序，是归并排序中用的最多的方法 。
如果数组中只有一个元素，这个数组是有序的。
或者更直观的来看：
实现方法：
public class testb {
public static void main(String[] args) {
MergeSort mergeSort = new MergeSort();
int arr[] = {
1, 4, 6, 8, 5, 3, 9, 34, 65, 23, 13, 84, -3, -4, -7, -1};
mergeSort.spilt(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
class MergeSort {
// 拆分方法
public void spilt(int[] arr, int startIndex, int endIndex) {
// 计算中间索引
int centerIndex = (startIndex + endIndex) / 2;
// 如果起始索引小于结束索引，则继续拆分，直到不能再拆为止
if (startIndex < endIndex) {
// 对左边继续拆分，左边序列的结束索引为中间点
spilt(arr, startIndex, centerIndex);
// 对右边继续拆分，右边序列的起始索引为中间点 + 1
spilt(arr, centerIndex + 1, endIndex);
// 拆分完成，进行归并
mergeSort(arr, startIndex, centerIndex, endIndex);
}
}
/**
* @param arr 原数组
* @param startIndex 左边数组的起始索引
* @param centerIndex 中间索引
* @param endIndex 右边索引的结束索引
*/
// 归并方法
public void mergeSort(int[] arr, int startIndex, int centerIndex, int endIndex) {
// 定义一个临时数组，由于要多次归并，所以数组长度是一直在变的，所以长度要设置为endIndex-startIndex+1
int[] tempArr = new int[endIndex - startIndex + 1];
// 定义左边数组的起始索引
int i = startIndex;
// 定义右边数组的起始索引（中间索引 + 1）
int j = centerIndex + 1;
int index = 0;
// 比较左右两个数组的元素大小，然后往临时数组中存放
while (i <= centerIndex && j <= endIndex) {
if (arr[i] <= arr[j]) {
tempArr[index] = arr[i];
i++;
} else {
tempArr[index] = arr[j];
j++;
}
index++;
}
// 由于数组长度奇偶不定，所以可能会存在剩余元素
// 处理剩余元素
// i<=centerIndex，说明左边元素有剩余
while (i <= centerIndex) {
tempArr[index] = arr[i];
i++;
index++;
}
// j<=endIndex，说明左边元素有剩余
while (j <= endIndex) {
tempArr[index] = arr[j];
j++;
index++;
}
// 把临时数组赋给原数组
for (int k = 0; k < tempArr.length; k++) {
arr[k + startIndex] = tempArr[k];
}
}
}
桶排序
思路：将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序
实现方法：
public class bucketSort {
public static void main(String[] args) {
int a[]= {
1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};
List[] buckets=new ArrayList[5];
for(int i=0;i<buckets.length;i++)//初始化
{
buckets[i]=new ArrayList<Integer>();
}
for(int i=0;i<a.length;i++)//将待排序序列放入对应桶中
{
int index=a[i]/10;//对应的桶号
buckets[index].add(a[i]);
}
for(int i=0;i<buckets.length;i++)//每个桶内进行排序(使用系统自带快排)
{
buckets[i].sort(null);
for(int j=0;j<buckets[i].size();j++)//顺便打印输出
{
System.out.print(buckets[i].get(j)+" ");
}
}
}
}
计数排序
计数排序是一种特殊的桶排序
思路：
- 找出待排序数组中的最大值和最小值
- 统计数组中每个值为 i 的元素出现的，存入数组C的第 i 项
- 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素 i 放在新数组的第 C( i )项，每放一个元素就将C( i )减去1。
实现方法：
class CountingSort{
public int[] countingSort(int[] arr) {
int maxValue = getMaxValue(arr);
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value : arr) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
public int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
}
基数排序
基数排序不需要对关键字进行比较，只需要对关键字进行“分配”与“收集“两种操作即可完成
思路：
创建10个桶，分别给定编号 0 - 9。对数组进行排序，第一轮比较，从数组顺序取出数字，每取出一个，放到编号与其个位的数字相对应的桶中，直到遍历完数组。这些桶可以看成是数组。
然后依次从 0 - 9 号桶取出存入的数字，组成新数组，进行第二轮比较，从数组顺序取出数字，每取出一个，放到编号与其十位的数字相对应的桶中，直到遍历完数组。
以此类推，数组中最大的数字为几位数，那就需要进行几轮
例如：一个数组为：{ 11，23，59，1，4，9，7，123，76，98，187，132，98，78，234 }
那么第一轮比较之后再取出的数组为：{ 11，1，132，23，123，4，234，76，7，187，98，98，78，59，9 }
第二轮比较之后取出的数组为：{ 1，4，7，9，11，23，123，132，234，59，76，78，187，98，98 }
第三轮比较之后取出的数组为：{ 1，4，7，9，11，23，59，76，78，98，98，123，132，187，234 }
此时数组排序完成
实现方法：
class BaseSort {
// 获取最大值的方法，用来确定需要比较的轮数
public int getMax(int[] arr) {
int max = arr[0];
// 因为max为arr[0],所以从 i = 1 开始比较
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
return max;
}
public void baseSort(int[] arr) {
int max = getMax(arr);
// 定义二维数组，放十个桶.每个桶最大长度是 arr.length
// 即：全部数字的个位都一样，此时桶达到最大长度
int[][] tempArr = new int[10][arr.length];
// 定义一个统计数组，用来统计每个桶中放了多少个元素
// 由于有10个桶，所以统计数组长度也为10
int[] count = new int[10];
// 比较轮次
int len = String.valueOf(max).length();
// k为除以的数字，求个位要除以1，求十位要除以10，依次类推
for (int i = 0, k = 1; i < len; i++, k *= 10) {
// 获取每个位上的数字
for (int j = 0; j < arr.length; j++) {
// remainder(余数): 为每个位上数字
int remainder = arr[j] / k % 10;
// count[remainder]++ 表示相应的桶中存入了一个数据
tempArr[remainder][count[remainder]++] = arr[j];
}
// 依次取出桶中的元素
int index = 0;
for (int m = 0; m < count.length; m++) {
// 如果该位置不为0，说明这个桶中有元素
if (count[m] != 0) {
for (int h = 0; h < count[m]; h++) {
arr[index] = tempArr[m][h];
index++;
}
// 每取出一个桶，则清除他统计的个数，因为下一轮还要存入
count[m] = 0;
}
}
}
}
}
注意：这里的算法只能排序正数，如果要排序负数，我们可以定义19个桶，十个为 0 - 9，还有九个桶为 （-1）- （-9）