java排序算法的示例分析
这篇文章将为大家详细讲解有关java排序算法的示例分析，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
一、直接插入排序
基本思想：
将一个记录插入到已排序的有序表中，使插入后的表仍然有序
对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序
package Sort;//插入排序public class InsertSort { public static void main(String[] args) { int [] arr={49,38,65,97,76,13,27,49}; sort(arr); print(arr); } private static void sort(int [] arr) { for (int i = 1; i < arr.length; i++) { for(int j=i;j>0;j--){ if(arr[j]<arr[j-1]){ swap(arr,j,j-1); } } } } private static void swap(int [] arr,int i,int j){ int temp=0; temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } private static void print(int [] arr) { for (int i = 0; i <arr.length ; i++) { System.out.print(arr[i]+" "); } }}13 27 38 49 49 65 76 97
Process finished with exit code 0
二、 希尔排序
希尔排序又称“缩小增量排序”（Diminishing Increment Sort)）属于插入排序类。
基本思想：
先将整个待排序的记录分割成若干子序列分别进行“直接插入排序”，待整个序列中的记录”基本有序“时，再对全体记录进行一次直接插入排序。
package Sort;//希尔排序是插入排序的改良public class ShellSort { public static void main(String[] args) { int [] arr={16,25,12,30,47,11,23,36,9,18,31}; sort(arr); print(arr); } private static void sort(int [] arr) { //gap设置优化 int h=1; while(h<arr.length/3){ h=h*3+1; } for(int gap=h;gap>0;gap=(gap-1)/3) {//gap:希尔排序的间距 for (int i = gap; i < arr.length; i++) { for (int j = i; j >gap-1; j-=gap) { if (arr[j] < arr[j - gap]) { swap(arr, j, j - gap); } } } } } private static void swap(int [] arr,int i,int j){ int temp=0; temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } private static void print(int [] arr) { for (int i = 0; i <arr.length ; i++) { System.out.print(arr[i]+" "); } }}9 11 12 16 18 23 25 30 31 36 47
Process finished with exit code 0
三、冒泡排序
冒泡排序
四、快速排序
对冒泡排序的一种改进
基本思想：
通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则可分别对这两部分记录继续分别进行排序，以达到整个序列有序。
package Sort;import java.util.Arrays;//快速排序public class QuickSort { public static void main(String[] args) { int[] arr={49,38,65,97,76,13,27,49}; sort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } private static void sort(int [] arr,int start,int end) { if(start<end){ //把数组的第0个数作为标准数 int stared=arr[start]; //记录要排序的下标 int low=start; int height=end; //循环找出比标准数大和比标准数小的数 while(low<height){ //右边数字比标准数大 while(low<height&&stared<=arr[height]){ height--; } //用右边的数字替换左边的数字 arr[low]=arr[height]; //左边数字比标准数小 while(low<height&&stared>=arr[low]){ low++; } //用左边的数字替换右边的数字 arr[height]=arr[low]; } arr[low]=stared; sort(arr,start,low); sort(arr,low+1,height); } } }[13, 27, 38, 49, 76, 97, 65, 49]
Process finished with exit code 0
五、选择排序(Selection Sort)
选择排序
六、堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
1、大顶堆举例说明：
我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子:
大顶堆特点：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点，i从0开始编号
2、小顶堆举例说明
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点，i从0开始编号
一般升序采用大顶堆，降序采用小顶堆
堆排序基本思想
一、堆排序的基本思想是：
将待排序序列构造成一个大顶堆
此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
二、代码示例
package Sort;import java.util.Arrays;public class HeapSort { public static void main(String[] args) { int [] arr={4,6,8,5,9}; heapSort(arr); } //编写一个堆排序的方法 public static void heapSort(int[] arr){ int temp=0; for(int i=arr.length/2-1;i>=0;i--){ adjustHeap(arr,i,arr.length); } //将堆顶元素与末尾元素进行交换，此时末尾就为最大值，将最大值全放在数组最后 //重新调整结构，使其满足堆定义，继续交换堆顶元素与当前末尾元素，反复执行调整交换步骤，使整个序列达到有序 for(int j=arr.length-1;j>0;j--) { //交换 temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, j); } System.out.println("数组"+Arrays.toString(arr)); } //将数组调整为一个大顶堆 public static void adjustHeap(int[]arr,int i,int length){ int temp=arr[i];//先取出当前元素的值，保存在临时变量中 //开始调整 //k=i*2+1;k是i节点的左子节点 for(int k=i*2+1;k<length;k=k*2+1){ if(k+1<length&&arr[k]<arr[k+1]){//说明左子节点的值小于右子节点的值 k++;//k指向右子节点 } if(arr[k]>temp){//如果子节点大于父节点 arr[i]=arr[k];//把较大的值赋给当前节点 i=k;//!!!i指向k，继续循环比较 }else{ break; } } //当for循环结束后，已经将以i为父结点的最大值放在了堆顶上（局部） arr[i]=temp;//将temp的值放在调整后的位置 }}堆排序结果：
数组[4, 5, 6, 8, 9]
七、归并排序
定义：
又一类不同的排序方法，将两个或两个以上的有序表合并成一个新的有序表。
需要辅助空间：O(n)
整个归并需要 [log2n] 趟
时间复杂度：O(nlog2n)
缺点：归并排序占用附加存储较多, 需要另外一个与原待排序对象数组同样大小的辅助数组。
优点：归并排序是一个稳定的排序方法
思路可以推广到“多路归并”
常用于外部排序
package Sort;//归并排序public class MergeSort { public static void main(String[] args) { int [] arr={4,5,7,8,1,2,3,6}; sort(arr); print(arr); } private static void sort(int [] arr) { int mid=arr.length/2; int[]temp=new int[arr.length]; int i=0;//标记左边数组 int j=mid+1;//标记右边数组起始点 int k=0; while(i<=mid&&j<arr.length){ if(arr[i]<=arr[j]){ temp[k]=arr[i]; i++; k++; }else{ temp[k]=arr[j]; j++; k++; } } while(i<=mid){temp[k++]=arr[i++];}//将左边剩余的，复制到数组 while(j<arr.length){temp[k++]=arr[j++];}//将右边剩余的，复制到数组 } private static void print(int [] arr) { for (int i = 0; i <arr.length ; i++) { System.out.print(arr[i]+" "); } }}1 2 3 4 5 6 7 8
Process finished with exit code 0
关于“java排序算法的示例分析”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
