排序算法
在评判一个排序算法优劣的时候，通常会使用到 时间复杂度 和 空间复杂度 这两个概念来帮助评判。那么这两个概念又是个什么样的东西呢？它们同时又表达着什么样的含义呢？
我们先来认识一下时间复杂度吧
1 时间复杂度
1.1 引入
要认识时间复杂度，得先需要了解 常数时间的操作
常数时间的操作：一个操作如果和数据量没有关系，每次都是 固定时间内完成的操作，叫做常数操作
e.g：
1.进行两个int类型整数的相加，无论参与计算的int整数值为多大消耗的时间都是一样的（位运算）
2.根据index进行数组的元素获取，不论index的大小消耗的时间都是一样的
现在可以进一步对时间复杂度进行一个理解
1.时间复杂度为一个算法流程中，常数操作数量的指标。常用O（读作big O）来表示。
具体来说，在常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，
剩下的部分如果记为f(N)，那么时间复杂度为O(f(N))
2.评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是常数项时间
接着，就通过一个例子来进行更进一步的理解吧
问：有序数组A，和无序数组B。需要获取存在B中同时也存在A中的数，A数组长度为N，B数组长度为M。
方法一：遍历数组B，并且遍历数组A，判断B中的每一个元素是否也存在A中
方法二：遍历数组B，对于B中的每一个元素使用二分查找判断是否在A中也存在
方法一：
遍历数组B时间为M，遍历数组A时间为N。
双层for循环时间复杂度为 M * N，也就是o(M * N)
方法二：
遍历数组B时间为M，遍历数组A时间为logN
双层for循环时间复杂度为M * logN，也就是o(M * logN)
1.2 解惑
估计大家看完上边还可能有些理解，接下来使用一个选择排序的例子来给大家解释说明一下选择排序的时间复杂度为什么是o(N ^ 2)
对乱序数组 {4, 8, 2, 6, 5, 1} 使用选择排序的方式进行排序，先看代码和结果
public static void selectionSort(int[] arr) {
// 此处i < arr.length - 1, 只会遍历 n - 1次（最后一次不需要进行遍历比较大小）
for (int i = 0; i < arr.length - 1; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++) {
// 记录更小数值的下标
if (arr[index] > arr[j]) {
index = j;
}
}
// 替换数值位置
if (index != i) {
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
原始数组和排序后的结果
选择排序之前：
4 8 2 6 5 1
选择排序之后：
1 2 4 5 6 8
待排序的数组元素一个有n个
第1次：从 0 ～ n-1 的下标中找到最小的元素放置到下标0上
第2次：从 1 ～ n-1 的下标中找到最小的元素放置到下标1上
...
第n-1次：从n-2 ~ n-1 的下标中到最小的元素防止到下标n-2上
（下标为n-1的数不再需要进行排序，在第n-1次的时候下标n-1数也被迫排好了）
那么从第1次到第n-1次，需要被遍历判断的数分别为
n n-1 n-2 ... 3 2
这个一个等差数列，利用高中的等差求和公式可以得到最终表达式的最高项就是N的平方（除去最高项的系数）
即选择排序的时间复杂度就是 o(N ^ 2)
2 排序
2.1 选择排序
见1.2中的代码，时间复杂度是o(N ^ 2)
2.2 冒泡排序
冒泡排序，故名思义就是多次遍历数组将当下最大的元素上浮，就像冒泡一样。网上已经有很多更好更详细解释了，这儿就直接贴代码出来啦。
public static void bubbleSort(int[] arr) {
for (int end = arr.length - 1; end > 0; end--) {
for (int i = 0; i < end; i++) {
// 将大的元素进行后移
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
2.3 插入排序
插入排序就是将新元素与原来已经排序好的数组最末一位进行比较大小。若新元素更大则不再比较直接添加到数组尾部，若新元素更小则和原数组最末位置换位置。然后再和原数组中倒数第二位进行比较。若新元素更大则不再比较，若新元素更小则和原数组倒数第二位置换位置，再和原数组中倒数第三位进行比较大小，类比往前直到数组头部。每一个新的元素都进行这样的比较逻辑。这儿也就直接贴代码啦。
public static void insertionSort(int[] arr) {
// 插入排序只从下标为1的位置开始排序
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
插入排序的时间复杂度的情况和数组元素原本的排列顺序有关
元素置换的优化
前边排序算法中进行元素置换的时候都使用到了临时辅助变量，下边代码可以不使用临时辅助变量达到置换的效果（原理使用到一个字符的异或的异或就是它自己本身）
public static void swap(int a, int b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
2.4 归并排序
归并排序使用到了递归想法和外排，时间复杂度为o(N * log N)。直接上代码
/**
* @param arr 待排序的数组
* @param L 数组的左边界，下标为0
* @param R 数组的右边界，下标为arr.length - 1
*/
public static void sortProcess(int[] arr, int L, int R) {
// 递归调用结束的条件:当数组长度为1时结束递归
if (L == R) {
return;
}
// 求取数组的中间位置
int mid = L + ((R - L) >> 1);
// 将数组切分成两段，分别进行排序
sortProcess(arr, L, mid);
sortProcess(arr, mid + 1, R);
// 将左右两个小数组进行合并且排序
merge(arr, L, mid, R);
}
/**
* 将两个原来已经排好序的数组进行合并且排序
*
* @param arr
* @param L
* @param mid
* @param R
*/
public static void merge(int[] arr, int L, int mid, int R) {
// 辅助数组
int[] help = new int[R - L + 1];
int i = 0;// 辅助数组的下标
int p1 = L;// 左边数组指针
int p2 = mid + 1;// 右边数组指针
// 循环遍历两个数组，进行降序排序（当有任何一个数组的指针到达边界就停止循环）
while (p1 <= mid && p2 <= R) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];// 进行判断的同时还更改数组的指针位置
}
// 当有一个小数组指针已经到达边界，则直接全部复制另一个数组剩余所有元素到help辅助数组中
// （两个数组中必定有一个已经到达边界，所以下边有且仅有一个循环条件成立）
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= R) {
help[i++] = arr[p2++];
}
// 复制数组元素且不破坏arr数组其他的元素
for (int j = 0; j < help.length; j++) {
arr[L + j] = help[j];
}
}
2.5 快排排序
快排基本的思路可以去参考经典的荷兰旗帜问题。时间复杂度是o(N ^ 2)，此处直接上代码
/**
* 快排主体方法，使用递归的方式
*
* @param arr
* @param L
* @param R
*/
public static void sortProcess(int[] arr, int L, int R) {
if (L < R) {
int[] p = partition(arr, L, R);
sortProcess(arr, L, p[0] - 1);
sortProcess(arr, p[1] + 1, R);
}
}
/**
* 每调用一次的结果是将数组排序为 小于原数组末尾元素 原数组末尾元素 大于原数组末尾元素
*
* @param arr
* @param L
* @param R
* @return
*/
private static int[] partition(int[] arr, int L, int R) {
int less = L - 1;
int more = R;
while (L < more) {
if (arr[L] < arr[R]) {
swap(arr, ++less, L++);
} else if (arr[L] > arr[R]) {
swap(arr, --more, L);
} else {
L++;
}
}
swap(arr, more, R);
return new int[]{less + 1, more};
}
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
2.6 堆排序
堆排序使用到了堆结构也就是使用到了完全二叉树，将数组抽象成一个完全二叉树。主要涉及到两个大步骤：构造大根堆，保证根节点元素值最大。时间复杂度是o(N * long N)
public static void heapSort(int[] arr) {
// 构建大根堆
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);// 依次进行0~i位大根堆的位置替换
}
// 1 将大根堆的根节点元素和堆尾位置元素交换，此时堆尾位置元素值是最大的
// 2 缩小堆大小，将堆重新构造为大根堆保证根节点元素值是最大的
// 3 重复 1 2 操作
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while (heapSize > 0) {
heapify(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
/**
* 将每一个节点元素值和其父节点元素值进行比较，保证父节点元素值大于子节点元素值。比较一直循环到根节点
*
* @param arr
* @param index
*/
public static void heapInsert(int[] arr, int index) {
// 子节点元素值和其父节点元素值进行比较，且一直到根节点结束
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);// 替换元素值
index = (index - 1) / 2;// 更改当下指针位置
}
}
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/**
* 判断父节点是否比子节点大，保证父节点元素值最大。最终保证所有的父子节元素值都比其孩子节点元素值大
*
* @param arr
* @param index
* @param heapSize
*/
public static void heapify(int[] arr, int index, int heapSize) {
// 当前父节点下标为index，计算出其左孩子节点下标
int left = index * 2 + 1;
// 一直循环判断父节点元素是否最大
// 左孩子下标必须小于堆的size
while (left < heapSize) {
// 获取最大孩子节点的下标
int largest = left + 1 < heapSize && arr[left] < arr[left + 1]// 判断右孩子是否存在且其元素值大于左孩子元素值
? left + 1
: left;
// 父节点元素值 和 最大孩子节点元素进行比较，获取最大节点元素的下标
largest = arr[index] > arr[largest] ? index : largest;
// 如果本来父节点元素值就是比其所有孩子节点元素值大的，不需要再进行元素替换和比较
if (largest == index) {
break;
}
// 替换节点元素值（只要当子节点元素值大于父节点元素值时才会执行）
swap(arr, largest, index);
index = largest;// 将index指向被替换的子节点下标（也就是原来比父节点元素值大的最大孩子节点下标）
left = index * 2 + 1;// 循环判断条件值更改，后边继续用于循环条件的判断
}
}
网友评论