栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

常见的排序算法(Java 版)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

常见的排序算法(Java 版)

目录

1.冒泡排序V1

2.冒泡排序V2

3.冒泡排序V3

二、鸡尾酒排序

三、快速排序


记录学习常见的排序算法。

1.冒泡排序V1

代码如下(示例):

     //冒泡排序
     public void bubbleSortingV1() {
         int[] arr= {9,1,88,89,99,72,76,33,25,35,86,25,12,172,65,44,49,83,75,};
         
         for(int i=0; i < arr.length; i++) {
             
             for(int j=0; j < arr.length - i -1; j++) {
                 if(arr[j] > arr[j+1]) {
                     int temp = arr[j];
                     arr[j] = arr[j+1];
                     arr[j+1] = temp;
                 }
             }
             System.out.printf("比较第" + (i+1) + "轮结果:" + Arrays.toString(arr)+ "n");
         } 
     }

 可以看出经过10轮排序后,数组已经为有序数组,不需要在进行额外排序。



2.冒泡排序V2

冒泡排序优化版本2,如果已经有序将,不再

代码如下(示例):

//冒泡排序
	 public void bubbleSortingV2() {
		 int[] arr= {9,1,88,89,99,72,76,33,25,35,86,25,12,172,65,44,49,83,75,};
		 
		 for(int i=0; i < arr.length; i++) {
			 boolean isOrdered = true;//是否有序, 默认为有序, 如果存在数据交换, 说明还未完成从小到大排序。
			 for(int j=0; j < arr.length - i -1; j++) {
				 if(arr[j] > arr[j+1]) {
					 int temp = arr[j];
					 arr[j] = arr[j+1];
					 arr[j+1] = temp;
					 isOrdered = false;
				 }
			 }			 		 
			 if(isOrdered) {
				 break;
			 }else {
				 System.out.printf("比较第" + (i+1) + "轮结果:" + Arrays.toString(arr)+ "n");
			 }
		 } 
	 }

增加数据交换标志,经过10轮将数组 排序成功。

3.冒泡排序V3

代码如下(示例):

     //冒泡排序
	 public void bubbleSortingV3() {
		 int[] arr= {9,1,88,89,99,72,76,33,25,35,86,25,12,172,65,44,49,83,75,};
		 
		 for(int i=0; i < arr.length / 2; i++) {
			 int sortBorder = arr.length -1;
			 boolean isSorted = true;
			 for(int j=0; j < sortBorder; j++) {
				 if(arr[j] > arr[j+1]) {
					 int temp = arr[j];
					 arr[j] = arr[j+1];
					 arr[j+1] = temp;
					 isSorted = false;
					 
				 }
			 }			 
			 if(isSorted) {
				 break;
			 }
			 else {
				 System.out.print("比较第" + i + "结果:" + Arrays.toString(arr) + "n");
			 }
			 
		 } 
	 }

二、鸡尾酒排序
     //排序
	 public void bubbleSortingV1() {
		 int[] arr= {9,1,88,89,99,72,76,33,25,35,86,25,12,172,65,44,49,83,75,};
		 long start = System.currentTimeMillis();
		 for(int i=0; i < arr.length / 2; i++) {
			 
			 boolean isSorted = true;//标记有序, 若没有数据交换,则为有序
			 //奇数轮,从左向右,比较 交换
			 for(int j=0; j < arr.length - i - 1; j++) {
				 if(arr[j] > arr[j+1]) {
					 int temp = arr[j];
					 arr[j] = arr[j+1];
					 arr[j+1] = temp;
					 isSorted = false; 
				 }
			 }			 
			 if(isSorted) {
				 break;
			 }
			 else {
				 //System.out.print("比较奇数轮,第" + (i +1) + "轮结果:" + Arrays.toString(arr) + "n");
			 }
			 
			 //在偶数轮开始排序之前,将isSorted 重新标记为true
			 isSorted = true;
			 //偶数轮,从右向左比较交换。
			 for(int j = arr.length - i - 1; j > i; j--) {
				 if(arr[j] < arr[j-1]) {
					 int temp = arr[j];
					 arr[j] = arr[j -1];
					 arr[j-1] = temp;
					 isSorted = false;
					 
				 }
				 
			 }
			 if(isSorted) {
				 break;
			 }
			 else {
				 //System.out.print("比较偶数轮,第" + (i +1) + "轮结果:" + Arrays.toString(arr) + "n");
			 }		 
			 System.out.print("比较偶数轮,第" + (i +1) + "轮结果:" + Arrays.toString(arr) + "n");
			 
		 }
		 System.out.print("排序公消耗:" + (System.currentTimeMillis() - start) + "毫秒");
	 }

 

三、快速排序
//冒泡排序
	 public void quickSortedV1() {
		 int[] arr= {9,1,88,89,99,72,76,33,25,35,86,25,12,172,65,44,49,83,75,};
		 long start = System.currentTimeMillis();
		 System.out.print("原始结果:" + Arrays.toString(arr) + "n");
		 quickSorting(arr, 0, arr.length - 1, 1);
		 System.out.print("排序公消耗:" + (System.currentTimeMillis() - start) + "毫秒");
	 }
	 
	 public void quickSorting(int[] arr, int startIndex, int endIndex, int lun) {
		 //递归函数基例:存在一个或过个不需再次递归条件。递归结束调件, startIndex>= endIdex
		 if(startIndex >= endIndex) {
			 return;
		 }
		 
		 int pivotIndex = getBasePositon(arr, startIndex, endIndex);
		 
		 quickSorting(arr, startIndex, pivotIndex -1, lun);
		 System.out.print("" + (lun++) + "轮结果:" + Arrays.toString(arr) + "n");
		 quickSorting(arr, startIndex + 1, endIndex, lun);
		 
		 System.out.print("" + (lun++) + "轮结果:" + Arrays.toString(arr) + "n");
		 				 
	 }
	 
	 public int getBasePositon(int[] arr, int sIndex, int eIndex) {
		 
		 int pivot = arr[sIndex];
		 int left = sIndex;
		 int right = eIndex;
		 
		 while(left != right) {
			 //控制right 指针比较并左移
			 while(left < right && arr[right] > pivot) {
				 right--;
			 }
			 
			 while(left < right && arr[left] <= pivot) {
				 left++;
			 }
			 
			 if(left < right) {
				 int p = arr[left];
				 arr[left] = arr[right];
				 arr[right] = p;
			 }
		 }
		 
		 arr[sIndex] = arr[left];
		 arr[left] = pivot;
		 
		 return left;
	 }

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/944126.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号