【数据结构与算法】二、算法门槛-简单排序与简单查找

大家好，我是春风。

算法在我们实际开发中，应用最广的场景就是排序和查找，所以今天总结一下所有入门级别的排序和查找算法，作为算法的入门~

什么是算法：

• 有具体的问题；
• 算法就是解决该问题的具体流程

时间复杂度：计算次数，只保留最高阶的N，去掉常数项。

时间复杂度相同的算法，则看具体的执行时间，常数项操作不一样，最终的计算时间也就不一样。

首先是选择排序、冒泡排序、插入排序，这三个排序的时间复杂度都是n^2；然后是归并排序、堆排序

选择排序是最直观的排序，就是比较N次，每次找到未排序数组里最小或者最大的数，然后放到已排序末尾。

代码：

int min;
for (int i=0; i arr[j]) {
            min = j;
        }
    }
    // 把找到的最小值放到i位置上
    if (min != i) {
        swap(arr[min] ,arr[i]);
    }
}

冒泡排序就是循环比较相邻的两个数，并按顺序交换位置，这样每次循环一次下来的结果就是最大或者最小值，会被放在首位或者末尾；

基础代码：

for(int i=0; i arr[j+1]) {// 交换相邻元素位置
            swap(arr[j], arr[j+1]);
        }
    }
}

优化一：

存在问题：如果在比较第a轮后（a

for(int i=0; i arr[j+1]) {// 交换相邻元素位置
            isSwap = true;
            swap(arr[j], arr[j+1]);
        }
    }
    
    // 比较一趟下来没有发生位置交换，则说明数组已经有序
    if (!isSwap) {
        break;
    }
}

优化二：

存在问题：如果数组前半段或者后半段本来就是有序的，那这部分的比较就是浪费的，所以加一个记录交换边界的值，每次只比较边界内数组元素。

int lastSwapIndex = 0;

for(int i=0; i arr[j+1]) {// 交换相邻元素位置
            isSwap = true;
            lastSwapIndex = j;
            swap(arr[j], arr[j+1]);
        }
    }

    sortBorder = lastSwapIndex;

    // 比较一趟下来没有发生位置交换，则说明数组已经有序
    if (!isSwap) {
        break;
    }
}

 插入排序就是每次比较相邻两个元素，将小的那个往前移动，一直到比较到头或者不用移动就停止。

比如每次比较第i 和第i-1 的大小，小的往前移动，然后继续比较 第i-1 和第i-2 的大小，如此循环。

插入排序最坏情况的时间复杂度是O(n^2)；但是当本来是有序的数组时，插入排序只用比较n次就可以停止，时间复杂度为O(n)

for (int i=0; i0 && arr[j-1] > arr[j]; j--) {
        // 否则 交换
        swap(arr[j-1], arr[j]);
    }
}

归并排序和二分查找思维方式有些类同，都是递归去处理一半的事物，归并是每次排好一半的元素的顺序。

递归通常会和栈这个结构结合，先入后出。

归并排序也可以想象成一颗二叉树的后序遍历，从叶子节点往上排序返回结果。

PS：关于二分之一下标的计算：

// 正常的计算数组中间下标的方式
int mid = (L+R)/2;

// 上面存在的问题，数组过大时，L+R会超出整型的范围
int mid = L + (R-L)/2;

// 优化：乘除2都可以直接用左移右移位运算
int mid = L + ((R-L) >> 1);

归并排序代码：

归并排序用的分而治之的策略，每次递归往下分左右两部分，直到分到每个部分只有一个数，然后每个部分都做好排序，并且合并。合并时，通过左右两个指针移动，将两部分数据比较大小然后合并在一起。

public static void mergeSort (int[] arr, int left, int right) {

   // 分到每一部分只有一个数，然后返回，做排序合并
   if (left >= right) {
      return;
   }

   int mid = left + ((right - left) >> 1);
   // 左边往下分
   mergeSort(arr, left, mid);
   //右边往下分
   mergeSort(arr, mid+1, right);

   // 将左右两部分进行排序
   merge(arr, left, right, mid);
}

// 排序合并
private static void merge(int[] arr, int left, int right, int mid) {

   // 定义左右两部分的起始指针，两个指针的数比较大小，小的放到临时数组，且将对应指针后移
   int p1 = left;
   int p2 = mid+1;
   int[] temp = new int[right-left+1];
   int i = 0;

   while (p1 <= mid && p2 <= right) {
      if (arr[p1] > arr[p2]) {
         temp[i++] = arr[p2++];
      } else {
         temp[i++] = arr[p1++];
      }
   }

   // 左边有剩下的，顺位加到临时数组
   while (p1 <= mid) {
      temp[i++] = arr[p1++];
   }

   // 右边有剩下的，顺位加到临时数组
   while (p2 <= right) {
      temp[i++] = arr[p2++];
   }

   // 数组赋值
   for (int j=0; j 
递归问题的时间复杂度计算：
 
像归并排序这种，子问题规模左右一致的，时间复杂度计算满足master公式
 
O(n) = a x (N/b) + 常数项操作的时间复杂度
 
a：递归处理子问题处理了多少次；
b：平均分成了多少份 ；
常数项操作指每次递归除了解决子问题外的操作-比如上面的merge排序合并；
所以，归并排序的时间复杂度通过master公式计算= Nlog(N)
 
归并排序为什么时间复杂度低？或者说排序的时候，每个元素的比较不重也不漏？
 
相比于选择、插入、冒泡等排序，归并排序中以某一个元素的比较历程来说，他先是分到最下层和右边相邻那个元素比较，然后合并成一个整体，再与右边部分进行比较，所以就比较次数来说，整体内不会重复的比较，而作为一个整体和右边比较的时候，指针最多移动到他这里比较一次，甚至有时候都移不到他这里，然后这个整体就比较完了，接下来只会再最多和右边部分的元素比较一次，节约了比较次数。
 
归并排序延伸问题：
 
1.求小和问题：一个数组，小和即某元素左侧小于他的元素的和，比如1，3，4，2，总小和 = 3的小和（1） + 4的小和（1+3） + 2的小和（1） = 6
 
求小和其实就是在上面的归并排序中，修改merge方法，每次merge的时候，当左指针指向的数小于右指针时，就证明，右指针及其右侧的元素的小和都有左指针指向的这个元素
 
左边部分：1,3 右边部分：2, 4
 
左指针指向1，右指针指向2 此时2比1大，则证明2的小和有1，且4的小和也有1；
 
代码：
 
public static int mergeSort (int[] arr, int left, int right) {

    // 分到每一部分只有一个数，然后返回，做排序合并
    if (left == right) {
        return 0;
    }

    int mid = left + ((right-left)>>1);

    return mergeSort(arr, left, mid) + mergeSort(arr, mid+1, right) + merge(arr, left, right, mid);
}

// 排序合并
private static int merge(int[] arr, int left, int right, int mid) {

    int res = 0;

    // 定义左右两部分的起始指针，两个指针的数比较大小，小的放到临时数组，且将对应指针后移
    int p1 = left;
    int p2 = mid+1;
    int[] temp = new int[right-left+1];
    int i = 0;

    while (p1 <= mid && p2 <= right) {
        
        res += arr[p1] < arr[p2] ? arr[p1]*(right-p2+1) : 0;

        
        temp[i++] = arr[p1] >= arr[p2] ? arr[p2++] : arr[p1++];
    }

    // 左边有剩下的，顺位加到临时数组
    while (p1 <= mid) {
        temp[i++] = arr[p1++];
    }

    // 右边有剩下的，顺位加到临时数组
    while (p2 <= right) {
        temp[i++] = arr[p2++];
    }

    // 数组赋值
    for (int j=0; j 
2.求逆序对：逆序对，就是右边的数比自己小，比如1,3,4,2,1。其中逆序对就有4,2、4,1、2,1，其实就是上面求小和反过来，求小和是左边比自己小的，逆序对是右边比自己小的，所以也是在merge方法里，找右边部分比自己小的情况。这里代码就不赘述了~
 
五、快速排序 
从荷兰国旗问题到快速排序
 
1、荷兰国旗问题：有一个数组，需要将大于num的数放在左边，等于num的数放到中间，大于num的数放到右边
 
这就是将一个数组按num分为三部分，因为荷兰国旗也是三个颜色的长方形组成，所以这个问题也被叫做荷兰国旗问题
 
解法：我们一般最快能想到的解法就是遍历一遍去比较，然后new三个数组来分别存放数据，但是这里要求空间复杂度为O1，所以我们只能在数组内操作，也就只能进行替换，所以解法就是在数组内指针移动比较，然后交换并存储左中右的临时边界。
 
遍历数组：
 
如果该元素大于num，则与右边界指针指向的值交换，同时右边界指针减一；
如果该元素等于num，则将i++，移动到下一个元素继续比较；
如果该元素小于num，则与左边界指针指向的元素交换，同时左边界指针加一；
2、快速排序
 
从上面的荷兰国旗问题，我们可以总结出规律，解决一次num的比较，其实针对num，数组就是有一定顺序了，等于num的那部分数就在排完序后的位置确定了。
 
那快排其实就是重复这个荷兰国旗的解决问题的方式，每次找最后一个数当做num，将数组分为三部分，然后在每部分再递归如此操作，继续找子部分里最后一个数做num，最后我们就一定能得到这样一个有顺序的数组。
 
快速排序的时间复杂度： 其实如果我们按最极端的情况来看，当一个数组本来是有序的，比如1,2,3,4,5 ，每次找最后一个数作为num，其实每次都只能分为一个部分，这样的情况，我们的时间复杂度就是O(N^2)，但是一般我们的快速排序会把最后一个数的方式换为取数组中随机一个数，这样根据概率，我们可能将数组分为1/2， 1/3 。。 然后每种出现的概率是1/N，最后我们通过计算得到的数学期望，其实得到的时间复杂度是NlogN
 
快速排序的空间复杂度：快排首先使用的额外空间是O(1)，但是在递归过程中，其实需要消耗空间来保存临时数组的，而在最优情况下，就是每次都能刚好二分，则消耗的空间复杂度为O(logN)，最差的情况就是数组本来就是有序的，每次只能分成一个部分，消耗的空间复杂度就是O(N)，所以和上面的时间复杂度计算一样，利用概率，计算出来的空间复杂度数学期望为：NlogN
 
代码：
 
public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        // 把数组中随机一个位置的数换到最后去，作为接下来划分区域的num
        swap(arr, left+(int)Math.random()*(right-left+1), right);
        int[] p = partition(arr, left, right);// 用num划分数组，得到左右边界
        quickSort(arr, left, p[0]-1);// 递归继续排左边
        quickSort(arr, p[1]+1, right);//递归继续排右边
    }
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static int[] partition(int arr[], int left, int right) {
    int less = left-1;// 左边界
    int more = right;//右边界

    while (left < more) {
        // left是移动的指针
        if (arr[left] < arr[right]) {
            // 当前元素小于目标元素，则和左边界元素交换，并且左边界加一，指针指向下一个元素比较
            swap(arr, ++less, left++);
        }else if (arr[left] > arr[right]) {
            // 当前元素大于目标元素，则和右边界元素交换，右边界减一，此时当前指针指的是换过来的还没比的元素，所以不变
            swap(arr, --more, left);
        } else {
            // 移动元素比较下一个
            left++;
        }
    }

    // 最后我们用来比较的num还在末尾，这里直接将右边界的值和num交换
    swap(arr, more, right);
    return new int[] {less+1, more};
}
 
简单查找 
简单查找这里看下最常用的二分查找
 
一、二分查找 
二分查找的核心就是每次都可以排除掉一半的元素，所以二分查找的时间复杂度主要就是看被砍一半，砍了多少刀？
 
每次砍一半，我们可以计算出一个大小为n的数组，最多可以被砍log₂N刀，举个例子： n = 8, 那砍一次->4, ->2 , ->1，一共可以看3次，2^3 = 8。
 
所以，二分查找的时间复杂度= O(log₂N)
 
1. 一个有序数组，找某个数是否存在？
 
标准的二分查找
 
int left = 0; //最左边下标
int right = len-1; // 最右边下标
int mid;
while(left <= right) {
    mid = (left + right) / 2; // 中间下标
    if (arr[mid] < k) {
        left = mid + 1;
    } else if (arr[mid] > k) {
        right = mid -1;
    } else {
        // 找到了
        break;
    }
}
 
2. 一个有序数组，找>=num的最左侧的数？
 
每次二分，缩小边界范围
 
比如 22334445555，找>=4的最左侧的值。
 
第一次二分，找到中间这个4，然后在左侧二分，中间的数小于4，则再取右侧部分二分。
 
3. 一个无序数组，找一个局部最小？
 
局部最小就是即小于他左边相邻的数，也小于他右边相邻的数（该无序数组元素都不相等）
 
这个问题数组虽然是无序的，但是也可以用二分，因为找局部最小，其实就是一个转折点，在如下这样一个区间里，是一定有这样一个转折点的，而我们每次二分就是去找这样的区间范围
 
> 4, 3, 2, 1    num     1, 2, 3, 4
> 
> ->依次变小    转折点   ->依次向上

每次二分，比如得到的区间是i - n ,则每次比较第i个数是否大于第i+1个数，且满足第n个数是否小于第n-1个数，
如果满足以上两个条件，则该区间符合，继续将该区间二分。
 

最后的最后，求点赞！非常感谢！
 
我是春风，春风和煦，不负归期！ 公H：程序员春风