题解 | #排序#
排序
http://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896
JAVA
一、插入排序
二、二分插入排序
三、Shell希尔插入排序
四、冒泡排序
五、快速排序
六、选择排序
七、调用库函数
八、归并排序
冒泡、插入排序，选择排序没有通过编译（可能因为复杂度不满足要求）
自己瞎写的，可能存在问题，欢迎指正。
一、插入排序（复杂度太高，不能通过）
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
int size=arr.length;
for(int i=1;i<size;++i){
int temp=arr[i];
int j=i-1;
while(j>=0 && arr[j]>temp){
arr[j+1]=arr[j];
j--;
}
if(j==-1)
arr[0]=temp;
else if(arr[j]<=temp){
arr[j+1]=temp;
}
}
return arr;
}
}二、二分插入排序
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
//折半插入
int size=arr.length;
for(int i=1;i<size;++i){
int left=0,right=i-1;
int temp=arr[i];
while(left<=right){
int mid=(left+right)/2;
if(temp<arr[mid]){
right=mid-1;
}else if(temp>=arr[mid]){
left=mid+1;
}
}
for(int j=i;j>left;--j){
arr[j]=arr[j-1];
}
arr[left]=temp;
}
return arr;
}
}三、Shell希尔插入排序
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
int size=arr.length;
int gap=size/2;
while(gap!=0){
for(int i=gap;i<size;++i){
int temp=arr[i];
int j;
for(j=i;j>=gap;j-=gap){
if(arr[j-gap]>temp)
arr[j]=arr[j-gap];
else break;
}
arr[j]=temp;
}
gap=gap/2;
}
return arr;
}
}四、冒泡排序（复杂度太高，不能通过）
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
int size=arr.length;
for(int i=1;i<size;++i){
int flag=1;
for(int j=size-1;j>=i;--j){
if(arr[j]<arr[j-1]){
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
flag=0;
}
}
if(flag==1) return arr;
}
return arr;
}
}五、快速排序
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
quickSort(arr,0,arr.length-1);
return arr;
}
void quickSort(int[] arr,int left,int right){
if(left>=right) return;
if(left<right){
int mid=partition2(arr,left,right);
quickSort(arr,left,mid-1);
quickSort(arr,mid+1,right);
}
}
int partition2(int[] arr,int left,int right){
int temp=arr[left];
while(left<right){
while(left<right && arr[right]>=temp)
right--;
arr[left]=arr[right];
while(left<right && arr[left]<=temp)
left++;
arr[right]=arr[left];
}
arr[left]=temp;
return left;
}
}六、选择排序（复杂度太高，不能通过）
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
int size=arr.length;
for(int i=0;i<size;++i){
int min= getMinIndex(arr,i,size-1);
swap(arr,i,min);
}
return arr;
}
void swap(int [] arr,int left,int right){
if(left==right) return;
int temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
}
int getMinIndex(int[]arr,int left,int right){
if(left>right) return -1;
else if(left==right) return left;
int min=arr[left];
int index=left;
for(int i=left+1;i<=right;++i){
if(arr[i]<min){
min=arr[i];
index=i;
}
}
return index;
}
}七、调用库函数
import java.util.*;
public class Solution {
public int[] MySort (int[] arr) {
// write code here
Arrays.sort(arr);
return arr;
}
}八、归并排序
import java.util.*;
import java.util.ArrayList;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
mergeSort(arr,0,arr.length-1);
return arr;
}
void mergeSort(int[] arr,int left,int right){
if(left>=right) return;
int mid=(left+right)/2;
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
merge(arr,left,mid,right);
}
void merge(int []arr,int left,int mid,int right){
if(left>=right) return;
int p1=left,p2=mid+1;
int []help = new int[right-left+1];
int count=0;
while(p1<=mid || p2<=right){
if(p1<=mid&&p2<=right){
if(arr[p1]<=arr[p2]){
help[count++]=arr[p1++];
}else help[count++]=arr[p2++];
}else if(p1<=mid && p2>right){
help[count++]=arr[p1++];
}else if(p1>mid && p2<=right){
help[count++]=arr[p2++];
}
}
for(int i=0;i<count;++i){
arr[left+i]=help[i];
}
}
}
