912. 排序数组

1.冒泡

1.想法

冒泡排序算法的原理如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2.伪代码

for i=n -> 1
  for j=0->i
   比较找出每次最大

3.代码

 public int[] sortArray(int[] nums) {
       //冒泡
        for(int i=nums.length-1;i>0;i--){
            for(int j=0;j<i;j++){
                if(nums[j]>nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
        return nums;
    }

2.快排

1.想法

设要排序的[数组](https://baike.baidu.com/item/%E6%95%B0%E7%BB%84)是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的[排序算法](https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95)，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是：

1）设置两个变量i、j，[排序](https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F)开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给**key**，即**key**=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于**key**的值A[j]，将A[j]和A[i]的值交换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于**key**的A[i]，将A[i]和A[j]的值交换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于**key**,4中A[i]不大于**key**的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

2.伪代码

1.以第一个数为基准,确定开头的i=start+1,j=end
2.如果i>=j,返回.否则进行第三步
3.从右向左找到一个比基准小的,从左向右找到一个比基准大的,且i<j,那么就交换 i>=j,那么结束循环
4.循环结束后将i与首位进行交换    
5.依次进行以上的循环        

3.代码

public int[] sortArray(int[] nums) {
       //快排
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    private void quickSort(int[] nums, int start, int end) {
        if(start >= end)return;   //返回结束
        int i=start,j=end;
        int standard = nums[start];
        while(i<j){                        
            while(i<j&&nums[j]>=standard)j--;//寻找右边小的
            while(i<j&&nums[i]<=standard)i++; //寻找左边大的
            if(i<j){                     //交换左大右小
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j]=temp;
            }
        }
        
        //将基准放到中间位置
        int temp = nums[i];
        nums[i] = nums[start];
        nums[start] = temp;
        
        
        quickSort(nums,start,i-1);
        quickSort(nums,i+1,end);
    }

3.堆排序

1.想法

https://www.jianshu.com/p/1977402d9277

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

2.伪代码

1.先建立大根堆或者小跟堆

2.交换堆顶元素,并每次将堆底的长度-1

3.重复2过程直到可选用对象为0

3.代码

public int[] sortArray(int[] nums) {
   //堆排
   for(int start = nums.length/2-1;start>-1;start--){
       adjust(nums,start,nums.length);
   }
   for(int i=nums.length-1;i>0;i--){
       swap(nums,i,0);
       adjust(nums,0,i);
   }
   return nums;
}

private void adjust(int[] nums, int start, int end) {
    if(start*2+1>=end)return;
    else if((start+1)*2>=end){
        if(nums[start*2+1]>nums[start]) {
            swap(nums, start, 2 * start + 1);
            adjust(nums,2*start+1,end);
        }
    }else{
        if(nums[start*2+1]<=nums[start]&&nums[(start+1)*2]<=nums[start])return;
        else if(nums[start*2+1]>nums[start]&&nums[start*2+1]>=nums[(start+1)*2]) {
            swap(nums, start, start * 2 + 1);
            adjust(nums,2*start+1,end);
        }
        else if(nums[(start+1)*2]>nums[start]&&nums[(start+1)*2]>nums[start*2+1]){
            swap(nums,start,start*2+2);
            adjust(nums,2*(start+1),end);
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

4.归并排序

1.想法

归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

总结:
分成两步:1.划分子问题.2.合并问题
1.如果子问题数组的长度大于1,再次划分,如果数组==1,停止划分,每次从中心点分开
2.合并每次与相邻的数组进行合并

2.伪代码

方法 mergesort(int[] nums,int left,int right)
   if left == right  说明现在只有一个元素,直接返回
   else  
       1.对现有的数组划分为两个,
       leftNums = nums [0,nums.length-1/2]
       rightNums = nums[nums.length-1/2+1,nums.length-1] 
       2.合并(1.申请数组空间,2.两个数组中小的放入3.两个数组中还有数字的那个放入最终的数组)
       int s=0,l=0,r=0;
       执行第一步:
       int[]  newNums = new int[left.length+right.length];
       执行第二步:
       while(l<left.length&&r<right.length)
         if(left[l]<=right[r])newNums[s++]=leftNums[l++];
         else newNums[s++]=right[r++];
       执行第三步:
         while(l<leftNums.length)  
             newNums[s++]=leftNums[l++];
         while(r<rightNums.length)
             newNums[s++]=rightNums[r++];

3.代码

public int[] sortArray(int[] nums) {
    //归并排序
    int[] newNums =mergeSort(nums,0,nums.length-1);
    return newNums;
}

private int[] mergeSort(int[] nums, int left, int right) {
    if(left == right) return new int[]{nums[left]};
    //1.对现有的数组划分为两个,
    int[] leftNums = mergeSort(nums,left,(right-left)/2+left);
    int[] rightNums = mergeSort(nums,(right-left)/2+left+1,right);
    // 2.合并(1.申请数组空间,2.两个数组中小的放入3.两个数组中还有数字的那个放入最终的数组)
    int s=0,l=0,r=0;
    //执行第一步:
    int[]  newNums = new int[leftNums.length+rightNums.length];
    //执行第二步:
    while(l<leftNums.length&&r<rightNums.length)
        if(leftNums[l]<=rightNums[r])newNums[s++]=leftNums[l++];
        else newNums[s++]=rightNums[r++];
    //执行第三步:
    while(l<leftNums.length)
        newNums[s++]=leftNums[l++];
    while(r<rightNums.length)
        newNums[s++]=rightNums[r++];
    return newNums;
}