常用的简单排序算法集合（更新中）

╰半橙微兮° 2022-01-14 07:31 297阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

/**
    	 * 冒泡排序
    	 */
    	public static void Bubble_Sort(int[] a) {
    		for (int i = 0; i < a.length - 1; i++) {
    			for (int j = 0; j < a.length - i - 1; j++) {
    				if (a[j] > a[j + 1]) {
    					a[i] = a[i] + a[j];
    					a[j] = a[i] - a[j];
    					a[i] = a[i] - a[j];
    				}
    			}
    		}
    	}
    
    	/**
    	 * 选择排序
    	 */
    	public static void Select_Sort(int[] a) {
    		int minIndex = 0;
    		for (int i = 0; i < a.length - 1; i++) {
    			minIndex = i;
    			for (int j = i + 1; j < a.length; j++) {
    				if (a[j] < a[minIndex]) {
    					minIndex = j;
    				}
    			}
    			if (minIndex != i) {
    				a[i] ^= a[minIndex];
    				a[minIndex] ^= a[i];
    				a[i] ^= a[minIndex];
    			}
    		}
    	}
    
    	// 插入排序
    	public static void Insert_Sort(int[] a) {
    		int length = a.length;
    		int insertval = 0;
    		int index = 0;
    		for (int i = 1; i < length; i++) {
    			insertval = a[i];
    			index = i - 1;
    			/**
    			 * 5 4 3 2 1
    			 * 4 5 3 2 1
    			 * 3 4 5 2 1
    			 * 2 3 4 5 1
    			 * 1 2 3 4 5
    			 */
    			while (index >= 0 && insertval < a[index]) {
    				a[index + 1] = a[index];
    				index--;
    			}
    
    			a[index + 1] = insertval;
    		}
    
    	}
    
    	/**
    	 * 快速排序——双向检索，返回调整后key的位置
    	 */
    	private static void part(int l, int r, int A[]) {
    
    		if (l < r) {
    			int i = l, j = r;
    			int key = A[i];// 取出收个数作为key，挖出第一个坑
    			while (i < j) {
    				// 循环从末尾找到第一个比key小或等于的数的索引j
    				while (i < j && A[j] > key)
    					j--;
    
    				if (i < j)
    					// 将这个比key小的数填入key处的坑，形成新坑索引j，同时增加索引i
    					A[i++] = A[j];
    				// 循环从i开始找到第一个打大于key的数字索引i
    				while (i < j && A[i] < key)
    					i++;
    
    				if (i < j)
    					// 将这个数填入上次的坑j内，同时j向下更新
    					A[j--] = A[i];
    			}
    			// 将key值填入中坑
    			A[i] = key;
    			part(l, i - 1, A);
    			part(i + 1, r, A);
    		}
    	}
    
    	/**
    	 * 快速排序——单向搜索 由小到大
    	 */
    	private static void part_single_s2b(int l, int r, int[] A) {
    
    		if (l < r) {
    			int i = l - 1;
    			int key = A[r];
    			for (int j = l; j < r; j++) {
    				if (A[j] > key) {
    					i++;
    					int tmp = A[i];
    					A[i] = A[j];
    					A[j] = tmp;
    				}
    			}
    			A[r] = A[i + 1];
    			A[i + 1] = key;
    			part_single_s2b(l, i, A);
    			part_single_s2b(i + 2, r, A);
    		}
    
    	}

关于快排序单扫描的解释：图摘自结构之法大神博客：[http://blog.csdn.net/v\_JULY\_v/article/details/6262915][http_blog.csdn.net_v_JULY_v_article_details_6262915]  
![26210947_1TwI.jpg][]  
关于挖坑填数的双向扫描：  
参加此大神博客：[http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html][http_www.cnblogs.com_morewindows_archive_2011_08_13_2137415.html]

Console：

=======随机数组100000个数据=======  
=======耗时0.014毫秒=======  
=======快速排序，双向扫描快速排序，生成有序数列=======  
=======耗时0.016毫秒=======  
=======快速排序，单向扫描快速排序，由大到小=======  
=======耗时0.232毫秒=======  
=======快速排序，双向扫描快速排序，由小到大=======  
=======耗时0.005毫秒=======  
=======冒泡排序，由小到大=======  
=======耗时2.541毫秒=======  
=======选择排序，由小到大=======  
=======耗时3.741毫秒=======  
=======插入排序，由小到大=======  
=======耗时0.004毫秒=======

转载于:https://my.oschina.net/u/1246663/blog/227120

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/46c7650846e94bb6896a2057f71c3ca4.png
[http_blog.csdn.net_v_JULY_v_article_details_6262915]: http://blog.csdn.net/v_JULY_v/article/details/6262915
[26210947_1TwI.jpg]: /images/20220114/63f7b9420ee7431cba4a771385d39db8.png
[http_www.cnblogs.com_morewindows_archive_2011_08_13_2137415.html]: http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html