[数据结构与算法]2021-08-15

排序算法

冒泡排序

将数组中的元素两两交换比较，每一轮交换都可以将未排序序列中的最大值找出来，放在已排序的序列末尾。
该排序算法的时间复杂度稳定为O(n^2)，空间复杂度为O(1)(直接在本数组上操作，不需要额外的存储空间)。
一种改进型的方法是判断某一轮循环中是否发生了元素交换，如果没有那么就表明排序已完成，不必在进行后续的排序。

void sort(int[] nums){
          boolean hasChange = true;
          for(int i=0; i < nums.length - 1 && hasChange; i++){
              hasChange = false;
              for(int j = 0; j < nums.length - 1 -i; j++){
                  if (nums[j] > nums[j + 1]){
                      swap(nums, j, j + 1);
                      hasChange = true;
                  }
              }
          }
      }

插入排序

不断地从未排序的数组中取出元素，插入到已排序的数组中。冒泡排序经过每一轮的排序，数组后端的数是排好序的；插入排序经过每一轮的排序，数组前端的数是排好序的。
插入排序的时间复杂度是O(n^2)，空间复杂度是n(1)

void sort1(int[] nums){
        for(int i=1; i < nums.length; i++){
            int current = nums[i];
            for(int j = i -1; j >= 0; j--){
                if (nums[j] < current){
                    nums[j + 1] = nums[j];
                }else{
                    nums[j + 1] = current;
                }
            }
        }
    }

归并排序

采用分治的思想，将一个问题分为多个小问题来求解。
具体地：
1）先将一个数组分成两个子数组；
2）递归地将每个子数组分割成更小的数组，直到数组中的元素个数是一个
3）依次按照递归的顺序返回，不断地合并排好序的子数组，直到把整个数组排好序
归并排序的需要创建一个新的大小为n的数组用于保存合并结果，所以空间复杂度是O(n)，时间复杂度是O(nlogn)

//主体代码
void mergeSort(int[] arr, int start, int end) {
    if (start >= end){
        return;
    }
    int mid = (start + end) /2;
    //递归滴分割
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    //无法在分割后合并
    merge(arr, start, mid, end);
}
//合并代码(思想：双指针法，left代表左子数组的起始位置，
//right代表右子数组的起始位置，k表示合并数组的当前位置)
void merge(int[] arr, int start, int mid, int end) {
    int tmpArr[] = new int[end - start + 1];
    int left = start;
    int right = mid + 1;
    int k = 0;
    //合并(left，mid)和(mid+1, end)两个有序小数组，采用了双指针法
    while(left <= mid && right<= end){
        if (arr[left] <= arr[right]){
            tmpArr[k++] = arr[left++];
        }else {
            tmpArr[k++] = arr[right++];
        }
    }
    while(left <=mid){//只剩余左子数组，将其加入到合并数组
        tmpArr[k++] = arr[left++];
    }
    while(right<=end){//只剩下右子数组，将其加入到合并数组
        tmpArr[k++] = arr[right++];
    }
    //将临时数组中的数据copy到arr中
    for (int m = 0; m < tmpArr.length; m++){
        arr[m + start] = tmpArr[m];
    }
}

快速排序

也是采用了分治思想，
1）选择其中一个元素作为基准数据，
2）将小于基准数据的放在左边，将大于基准数据的放在右边，
3）然后继续对左右两个子数组采用快速排序。当子数组的元素个数为1，也就排好了子数组。
空间福再度O(logn)，平均时间复杂度O(nlogn)

void quitSort(int[] nums, int low, int height) {
    if (low >= height){
        return;
    }
	//分区函数，找到一个标准值，将数组分为左右两部分
    int p = partition(nums, low, height);
    //对左半部分递归调用快速排序
    quitSort(nums, low, p - 1);
    //对右半部分递归调用快速排序
    quitSort(nums, p + 1, height);
}
//分区函数实现
int partition(int[] nums, int low, int height) {
	//随机选择一个座位基准值，将基准值与最有边的数交换，
	//这样num[height]就是基准值
    swap(nums, randRange(low, height), height);
    int i, j;
    for(i = low, j = low; j < height; j++){
    	//小于基准值的放在数组左边
        if (nums[j] < nums[height]){
            swap(nums, i++, j);
        }
    }
    //循环到最后j=height，也就是基准值，将nums[i]与基准值交换
    //这样左边的都是小于基准值的，i右边的都是大于基准值的
    swap(nums, i, j);
    return i;//交换后nums[i]就是基准值，i就是基准值下标，返回该下标。
}