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;
}
