常用排序代码实现
快速排序
public class QuickSort{
public int[] sortArray(int[] nums){
if(nums.length<2){
return nums;
}
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort(int[] nums,int left,int right){
if(left>=right){
return;
}
int position=partition(nums,left,right);
quickSort(nums,left,position-1);
quickSort(nums,position+1,right);
}
public int partition(int[] nums,int left,int right){
int pivotIdx=new Random().nextInt(right-left+1)+left;
swap(nums,pivotIdx,left);
int i=left+1;
int j=right;
while(true){
while(i<=right && nums[i]<pivot){
i++;
}
while(j>left && nums[j]>pivot){
j--;
}
if(i>=j){
break;
}
swap(nums,i,j);
i++;
j--;
}
swap(nums,left,j);
return j;
}
private void swap(int[] array,int i,int j){
if(i==j){
return;
}
array[i]^=array[j];
array[j]^=array[i];
array[i]^=array[j];
}
public static void main(String[] args){
int[] data=new int[10];
for(int i=0;i<10;i++){
data[i]=new Random().nextInt(11);
}
System.out.print("排序前"+Arrays.toString(data)+"\n");
long start=System.currentTimeMillis();
new QuickSort().sortArray(data);
long end=System.currentTimeMillis();
System.out.print("排序后"+Arrays.toString(data)+"\n");
System.out.print("耗时："+(end-start)+"ms");
}
}
堆排序
public class HeapSort{
public int[] sortArray(int[] nums){
headSort(nums);
return nums;
}
//step3:堆排序
public void headSort(int[] nums){
int len=nums.length-1;//区间最后一个位置（下标）
//先针对nums构建大顶堆
buildMaxHeap(nums,len);
/*
将堆顶元素和堆最后一个元素交换，有序数据多了一个，堆中数据少一个，
然后针对交换过来的堆顶元素进行堆化调整
依次操作直到堆中只剩一个元素（只需进行len-1次交换），整体数据有序
*/
for(int i=len;i>=1;i--){
swap(nums,0,1);
len--;
//堆化调整
maxIfyDown(nums,0,len);
}
}
//step2:针对nums构建大顶堆
public void buildMaxHeap(int[] nums,int end){
//为了能使用从上到下的堆化调整，我们从倒数第二层最后一个元素开始进行调整
for(int i=(end-1)>>1;i>=0;i--){
maxIfyDown(nums,i,end);
}
}
//step:在区间[start,end]进行从上到下的堆化调整
public void maxIfyDown(int[] nums,int start,int end){
while(start<=(end-1)>>1){
int lson=(start<<1)+1;
int rson=lson+1;
//找自己，左孩子，有孩子中最大值替换自己
int large=start;
if(lson<=end && nums[lson]>nums[large]){
large=lson;
}
if(rson<=end && nums[rson]>nums[large]){
large=rson;
}
//如果最大值来自左右孩子，交换
if(large!=start){
swap(nums,start,large);
//到下一层继续
start=large;
}else{
break;
}
}
}
private void swap(int[] array,int i,int j){
if(i==j){
return;
}
array[i]^=array[j];
array[j]^=array[i];
array[i]^=array[j];
}
public static void main(String[] args){
int[] data=new int[]{5,2,6,9,0,3};
System.out.print("排序前"+Arrays.toString(data)+"\n");
new HeapSort().sortArray(data);
System.out.print("排序后"+Arrays.toString(data)+"\n");
}
}
插入排序
public static void insertionSort(int[] data){
int len=data.length;
if(len<2){
return;
}
int preIdx,current;
for(int i=1;i<len;i++){
current=data[i];
preIdx=i-1;
while(preIdx>=0 && data[preIdx]>current){
data[preIdx+1]=data[preIdx];
preIdx--;
}
data[preIdx+1]=current;
}
public static void main(String[] args){
int[] data=new int[]{5,2,6,9,0,3};
System.out.print("排序前"+Arrays.toString(data)+"\n");
insertionSort(data);
System.out.print("排序后"+Arrays.toString(data)+"\n");
}
}
归并排序
public class mergeSort{
int[] temp;
public int[] sortArray(int[] nums){
temp=new int[nums.length];
mergeSort(nums,0,nums.length-1);
return nums;
}
public void mergeSort(int[] nums,int left,int right){
if(left>=right){
return;
}
int mid=(left+right)>>1;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
//填充临时空间
int i=left;
int j=mid+1;
int k=0;
while(i<=mid && j<=right){
if(nums[i]<=nums[j]){
tem[k++]=nums[i++];
}else{
tem[k++]=nums[j++];
}
}
while(i<=mid){
temp[k++]=nums[i++];
}
while(j<=right){
temp[k++]=nums[j++];
}
for(int m=right;m>=left;m--){
nums[m]=temp[--k];
}
}
public static void main(String[] args){
int[] data=new int[]{5,2,6,9,0,3};
System.out.print("排序前"+Arrays.toString(data)+"\n");
int[] mergeSort=new mergeSort().sortArray(data);
System.out.print("排序后"+Arrays.toString(mergeSort)+"\n");
}
}
原文地址：https://blog.csdn.net/linux_lzj_cainiao/article/details/144367456
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！