常见的排序算法,如快速排序,堆排序,插入排序
2021/11/11 22:13:22
本文主要是介绍常见的排序算法,如快速排序,堆排序,插入排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
public class TestDemo1 { //插入排序 public static void insertSort(int[] arr){ for(int i=1;i<arr.length;i++){ int temp=arr[i]; int j; for(j=i-1;j>=0;j--){ if(arr[j]>temp){ arr[j+1]=arr[j]; }else{ break; } } arr[j+1]=temp; } } //希尔排序 public static void shellSort(int arr[]){ int[] gap={3,2,1}; for(int i=0;i<gap.length;i++){ insertSort(arr,gap[i]); } } public static void insertSort(int[] arr,int gap){ for(int i=gap;i<arr.length;i++){ int temp=arr[i]; int j; for(j=i-gap;j>=0;j=j-gap){ if(temp<arr[j]){ arr[j+gap]=arr[j]; }else{ break; } } arr[j+gap]=temp; } } //选择排序 public static void selectSort(int[] arr){ int minIndex; for(int i=0;i<arr.length;i++){ minIndex=i; for(int j=i+1;j<arr.length;j++) { if (arr[minIndex] > arr[j]) { minIndex = j; } } if(minIndex!=i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } //堆排序 //向下调整函数 public static void shiftDown(int len,int[] arr){ int parent; for(int i=(len-1-1)/2;i>=0;i--) { parent=i; int child = parent * 2 + 1; while (child < len) { if (child + 1 < len && arr[child] <arr[child+1]) { child++; } if (arr[child] > arr[parent]) { int temp = arr[child]; arr[child] = arr[parent]; arr[parent] = temp; parent = child; child = parent * 2 + 1; } else { break; } } } } public static void heapSort(int[] arr){ shiftDown(arr.length,arr);//调整为大根堆 for(int i=arr.length-1;i>0;i--){//堆排序 int temp=arr[i]; arr[i]=arr[0]; arr[0]=temp; shiftDown(i,arr); } } //冒泡排序 public static void bubbleSort(int[] arr){ boolean flag = false; for(int i=0;i<arr.length;i++){ for(int j=0;j<arr.length-1-i;j++){ if(arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; flag=true; } } if(flag==false){ break; } } } //快速排序 public static int partition(int[] arr,int i,int j){ int privot=arr[i]; while(i<j){ // while(i<j && arr[j]>=privot){ j--; } arr[i]=arr[j]; while(i<j && arr[i]<=privot){ i++; } arr[j]=arr[i]; } arr[i]=privot; return i; } public static void quickSort(int[] arr,int start,int end){ if(start>end){ return; } int partition=partition(arr,start,end);// 得到基准 quickSort(arr,start,partition-1);// 向基准左递归 quickSort(arr,partition+1,end);// 向基准右递归 } }
图解:
这篇关于常见的排序算法,如快速排序,堆排序,插入排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)