目录
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 小和问题
- 逆序对问题
冒泡排序
冒泡排序的思路：每一个数与自己后面的数比较，如果前者>后者，则交换，直到最大的数排到了最后；下一轮继续执行同样操作，直到第二最大数拍到了倒数第二个位置。以此类推，每一轮确定一个数最终位置，需要比较的数在递减，直到所有循环结束为止。
外层循环：0～N-1位置找出来最大的放在N-1位置 ，N每轮递减。
内层循环：比较两个相邻的数，如果前者>后者，则交换
public static void bubbleSort(int[] arr) {
if(arr == null || arr.length < 2){
return;
}
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);
}
}
}
}
冒泡排序的时间复杂度为O(N^2)，额外空间复杂度为O(1)。
选择排序
选择排序的思路：循环遍历选出最小的一个数放在第一个位置；下一轮再在第二个位置开始遍历，选出最小的一个数放在第二个位置。以此类推，每一轮选出最小数排到前面，每一轮需要比较的数在递减，直到所有循环结束为止。
外层循环：0～N-1位置找出来最大的放在0位置。
内层循环：找到最小数的下标，然后交换
public static void selectSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for(int i = 0; i < arr.length; i++){
int minIndex = i;
for(int j = i + 1; j < arr.length; j++){
if(arr[minIndex] > arr[j]){
swap(arr, minIndex, j);
}
}
}
}
选择排序的时间复杂度为O(N^2)，额外空间复杂度为O(1)。
插入排序
插入排序的思路：将一个数组数据分为有序组和待插入组，每一次从待插入组中去一个数，与有序组中的元素进行对比，并找到合适的位置插入到有序组。每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。
外层循环：从左至右每次从待插入组中取一个元素进行比较
内层循环：将这一元素与有序组中的元素进行对比，找到合适的位置插入。
public static void insertionSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for(int i = 1; i < arr.length; i++){
for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--){
swap(arr, j, j + 1);
}
}
}
插入排序的时间复杂度为O(N^2)，额外空间复杂度为O(1)。
归并排序
归并排序的思路：归并排序采用分治法，将数组一分为二，层层向下划分，直到子数组只剩下一个数无法划分为止，然后将相邻的两个数组进行有序合并，层层向上合并，最终完成有序归并。
归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
public static void mergerSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergerSort(arr, 0, arr.length - 1);
}
public static void mergerSort(int[] arr, int left, int right) {
// 当无法再划分时返回
if (left == right) {
return;
}
// 将数组划分为左右两个数组，再通过递归向下划分
int mid = (left + right) / 2;
mergerSort(arr, left, mid);
mergerSort(arr, mid + 1, right);
// 将两个有序数组合并
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right){
// 将两个有序的数列合并成一个大的有序的序列
int[] help = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
while (p1 <= mid && p2 <= right){
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
//当上一个循环将某一个数组全部填入大数组后，另一个数组也依次全部填入
//下面两个wihle循环只会执行一个
while (p1 <= mid){
help[i++] = arr[p1++];
}
while (p2 <= right){
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++){
arr[left + i] = help[i];
}
}
归并排序的时间复杂度为O(N * logN)，额外空间复杂度为O(N)。
小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子：[1,3,4,2,5]
- 1左边比1小的数，没有；
- 3左边比3小的数，1；
- 4左边比4小的数，1、3；
- 2左边比2小的数，1；
- 5左边比5小的数，1、3、4、2；
- 所以小和为1+1+3+1+1+3+4+2=16
小和问题可以把问题理解成，左边的数寻找右边到底有几个比自己大的数，如果右边的数组是一个有序数组，那么只需要找到第一个比自己大的数，就可以得出这个数的右侧都比自己大，从而不需要重复比较。
理解了这一层意思，就可以将小和问题和归并排序同样看待，除了需要排序以外，还需要在merge的时候得出右侧数组有几个比自己大的数。
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return mergerSort(arr, 0, arr.length - 1);
}
public static int mergerSort(int[] arr, int left, int right) {
if (left == right) {
return 0;
}
//同样的merge操作，将每次merge得出的小和相加
int mid = (left + right) / 2;
int leftSum = mergerSort(arr, left, mid);
int rightSum = mergerSort(arr, mid + 1, right);
int mergeSum = merge(arr, left, mid, right);
return leftSum + rightSum + mergeSum;
}
public static int merge(int[] arr, int left, int mid, int right){
int[] help = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
int sum = 0;
while (p1 <= mid && p2 <= right){
//由于右边数组是有序的，所以只需要找到第一个比自己大的数，就可以得出后面的数都比自己大
//从而乘以后面数的个数就可以得到自己的小和
sum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid){
help[i++] = arr[p1++];
}
while (p2 <= right){
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++){
arr[left + i] = help[i];
}
return sum;
}
逆序对问题
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。
如果小和问题是左边的数寻找右边到底有几个比自己大的数，那么逆序对问题就是左边的数寻找右边有几个比自己小的数，算法与归并排序基本一致。
public static void reverseOrder(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergerSort(arr, 0, arr.length - 1);
}
public static void mergerSort(int[] arr, int left, int right) {
if (left == right) {
return;
}
int mid = (left + right) / 2;
mergerSort(arr, left, mid);
mergerSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right){
int[] help = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
while (p1 <= mid && p2 <= right){
//左边数组是有序的，所以只需要找到第一个比自己小的数，那么左边数组后面的数都比该数大。
if(arr[p1] > arr[p2]){
for(int j = p1; j <= mid; j++){
System.out.println(arr[j]+":"+arr[p2]);
}
}
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid){
help[i++] = arr[p1++];
}
while (p2 <= right){
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++){
arr[left + i] = help[i];
}
}
参考资料：牛客网左程云初级算法教程
