分类
- 比较类排序 : 通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序.
- 非比较类排序 : 不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序.
- ?稳定 : 如果a原本在b前面,而a=b,排序之后a仍然在b的前面
- 不稳定 :?如果a原本在b前面,而a=b,排序之后a可能会出现在b的后面
- 时间复杂度 : 对排序数据的总的操作次数.反映当n变化时,操作次数呈现什么规律
- 空间复杂度 :?是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函
1.选择排序?
? ? ? ??选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小(大)元素，继续放在起始位置知道未排序元素个数为0。
?排序步骤:?
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的起始位置。
- 重复第二步，直到所有元素均排序完毕。
public static void selectSort(int[] arr) {
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;
}
}
swap(arr,i,min);
}
print(arr);
}
- 选择排序是不稳定的排序算法
- 选择排序的时间复杂度为O(n2) ,空间复杂度为O(1)
- 基本不用,不稳
2.冒泡排序?
? ? ? ? 冒泡排序是比较基础的排序算法之一，其思想是相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。
?排序步骤:?
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 每趟从第一对相邻元素开始，对每一对相邻元素作同样的工作，直到最后一对。
- 针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较。
public static void bubbleSort(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr,j,j+1);
}
}
}
print(arr);
}
- 冒泡排序是稳定的排序算法
- 冒泡排序的时间复杂度为O(n2) ,空间复杂度O(1)
- 基本不用,太慢
3.插入排序?
? ? ? ? 插入排序也是一种常见的排序算法，插入排序的思想是：将初始数据分为有序部分和无序部分，每一步将一个无序部分的数据插入到前面已经排好序的有序部分中，直到插完所有元素为止。
??排序步骤:?
? ? ? ? 每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。
?
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr,j,j-1);
}
}
}
print(arr);
}
- 插入排序是稳定的排序算法
- 插入排序的时间复杂度为O(n2) ,空间复杂度O(1)
- 样本小且基本有序的时候效率比较高
4.希尔排序
? ? ? ? 希尔排序又称为缩小增量排序，是对之前介绍的插入排序的一种优化版本，优化的地方在于：不用每次插入一个元素时，就和序列中有序部分中的所有元素进行比较。
??该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于序列元素总数）作为间隔，所有距离为increment的元素放在同一个逻辑数组中，在每一个逻辑数组中分别实行直接插入排序。然后缩小间隔increment，重复上述逻辑数组划分和排序工作。直到最后取increment=1，将所有元素放在同一个数组中排序为止。
排序步骤:?
- 选increment，划分逻辑分组，组内进行直接插入排序。
- 不断缩小increment，继续组内进行插入排序。
- 直到increment=1，在包含所有元素的序列内进行直接插入排序。
?
public static void shellSort(int[] arr) {
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
for (int j = i; j > gap - 1; j -= gap) {
if (arr[j] < arr[j - gap]) {
swap(arr,j,j-gap);
}
}
}
}
print(arr);
}
- 希尔排序是不稳定的排序算法
- 希尔排序的时间复杂度为O(n^1.3) ,空间复杂度O(1)
?5.归并排序
? ? ? ? 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治(divide- and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
?
?
public static void mergeSort(int[] arr, int left, int right) {
if (left == right) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid + 1, right);
}
public static void merge(int[] arr, int leftPtr, int rightPtr, int rightBound) {
int mid = rightPtr - 1;
int[] temp = new int[rightBound - leftPtr + 1];
int i = leftPtr;
int j = rightPtr;
int k = 0;
while (i <= mid && j <= rightBound) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= rightBound) {
temp[k++] = arr[j++];
}
for (int n = 0; n < temp.length; n++) {
arr[leftPtr + n] = temp[n];
}
}
- 归并排序是稳定的排序算法
- 归并排序的时间复杂度为O(nlogn) ,空间复杂度O(n)
Java对象排序?
?对象排序一般要求稳定
6.快速排序?
? ? ? ? 快速排序的思想是：每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。
单路快速排序?
排序步骤:?
- 先从数列中取出一个数作为基准数
- 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
- 再对左右区间重复第二步,直到各区间只有一个数
public static void quickSort(int[] arr,int leftBound,int rightBound) {
if (leftBound >= rightBound) {
return;
}
int mid = partition(arr,leftBound,rightBound);
quickSort(arr,leftBound,mid-1);
quickSort(arr,mid+1,rightBound);
}
public static int partition(int[] arr,int leftBound,int rightBound) {
int pivot = arr[rightBound];
int left = leftBound;
int right = rightBound - 1;
while (left <= right) {
while (left <= right && arr[left] <= pivot) {
left++;
}
while (left <= right && arr[right] > pivot) {
right--;
}
if (left < right) {
swap(arr,left,right);
}
}
swap(arr,left,rightBound);
return left;
}
- 快速排序是不稳定的排序算法
- 快速排序的时间复杂度为O(nlogn) ,空间复杂度O(logn)
?7.计数排序
? ? ? ? 计数排序的基本思想就是：加入输入一个数x，如果我们可以找到比x小的数有几个，那么就可以直接将x放入到对应的输出数组的位置。
?排序步骤:?
- 统计数组A中每个值A[i]出现的次数，存入C[A[i]]；
- 从前向后，使数组C中的每个值等于其与前一项相加，C[A[i]]代表数组A中有多少个小于等于A[i]的元素；
- 反向填充目标数组B：将数组元素A[i]放在数组B的第C[A[i]]个位置（下标为C[A[i]] – 1），每放一个元素就将C[A[i]]递减。
public static int[] countSort(int[] arr) {
int max = arr[0];
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
int[] result = new int[arr.length];
int[] count = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
for (int i = 1; i < count.length; i++) {
count[i] = count[i] + count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
result[--count[arr[i]] - min] = arr[i];
}
return result;
}
- 计数排序是稳定的排序算法
- 计数排序的时间复杂度为O(n+k) ,空间复杂度O(n+k)
- 数据量大且范围小
- 桶思想的一种
8. 基数排序
? ? ? ? 基数排序是将整数按位数切割成不同的数字，然后按每个位数分别比较从而得到有序的序列。
?排序步骤:??
- 获取数中最大的元素
- 获取最大元素的长度maxLength
- 定义一个二维数组存储各元素在对应桶中的具体位置
- 定义一个一维数组长度为10，用于存储各个桶中元素的个数
- 外层for循环，使用maxLength控制循环次数，同时，每次循环取的是不同位数上的元素，所以需要定义变量n=1且n在每一轮循环结束后要*10
- 内层for循环，根据需要排序的数组arr的长度，控制循环次数
- 每次内层循环结束，即一轮排序结束，需要按照桶的顺序，从左向右，按照桶中元素存放的顺序：从上到下 依次取出元素，组成新的数组
public static void radixSort(int[] arr) {
//得到数组中最大的数的位数
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int size = (max + "").length();
//定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
int[][] bucket = new int[10][arr.length];
//每个桶存入了几个数字
int[] everyBucketNum = new int[10];
for (int i = 0, n = 1; i < size; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
//取出每个元素的对应位的值
int digit = arr[j] / n % 10;
//放入到对应的桶中
bucket[digit][everyBucketNum[digit]] = arr[j];
everyBucketNum[digit]++;
}
//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
int index = 0;
for (int k = 0; k < everyBucketNum.length; k++) {
if (everyBucketNum != null) {
for (int l = 0; l < everyBucketNum[k]; l++) {
arr[index++] = bucket[k][l];
}
}
//放回原数组后，需要将每个 everyBucketNum[k] = 0
everyBucketNum[k] = 0;
}
}
print(arr);
}
- 基数排序是稳定的排序算法
- 基数排序的时间复杂度为O(n*k) ,空间复杂度O(n*k)
- 本质上是一种多关键字排序
- 有低位优先和高位优先两种(LSD? MSD[分治思想])
9.桶排序?
? ? ? ? 桶排序也是时间复杂度仅为 O(n) 的一种排序方法，它假设输入数据服从均匀分布，我们将数据分别放入到 n 个桶内，先对桶内数据进行排序，然后遍历桶依次取出桶中的元素即可完成排序。和计数排序类似，桶排序也对输入数据作了某种假设，因此它的速度也很快。具体来说，计数排序假设了输入数据都属于一个小区间内的整数，而桶排序则假设输入数据是均匀分布的，即落入每个桶中的元素数量理论也是差不多的，不会出现很多数落入同一个桶内的情况。
- 桶排序是稳定的排序算法
- 桶排序的时间复杂度为O(n) ,空间复杂度O(n+k)
10.堆排序
- 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序
- 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆,注意:没有要求结点的左孩子的值和右孩子的值的大小关系。
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
排序步骤:??
- 将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
- 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
- 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,
- 直到整个序列有序。
最大堆构建步骤:?
- ?将待排序序列构造成一个大顶堆
- 此时，整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换，此时末尾就为最大值。
- 然后将剩余n-1 个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
?
?
public static void heapSort(int[] arr) {
//1.构建大顶堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr, i, arr.length);
}
//然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
//2.调整堆结构+交换堆顶元素与末尾元素
for (int j = arr.length - 1; j > 0; j--) {
swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr, 0, j);//重新对堆进行调整
}
print(arr);
}
/**
* 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上, 也就是说只调用一次,并没有得到大顶堆）
* 就是将arr[i] 的值放到本次 调整过程中适当的位置。
*
* @param arr : 数组
* @param i : 非叶子节点的索引
* @param length : 对多少个元素进行调整，这个length是逐渐减少的..
*/
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];//先取出当前元素i
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2*i+1处开始
if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点，k指向右子结点
k++;
}
if (arr[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];//把较大的值，赋给当前节点
i = k;//i 指向k,继续循环比较
} else {
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
- 堆排序是不稳定的排序算法
- 堆排序的时间复杂度为O(nlogn) ,空间复杂度O(1)