排序算法：冒泡排序和快速排序

蔚落 2022-02-01 04:21 316阅读 0赞

排序算法基本上是程序员必要掌握的一种技能；针对不同的数据特点采用不同的算法将会提高程序的效率，大大的节省资源。排序算法有很多种如插入排序、选择排序、冒泡排序、快速排序、归并排序、希尔排序、二叉树排序、计数排序、桶排序等等；但是本文就简单的先介绍一下冒泡排序和快速排序两种：

冒泡排序应该属于稳定的排序算法；而快速排序则属于不稳定的排序算法。

冒泡排序：名字已经很形象，实际实现是相邻两节点进行比较，大的向后移一个，经过第一轮两两比较和移动，最大的元素移动到了最后，第二轮次大的位于倒数第二个，依次进行。

快速排序：首先找到一个基数，一般情况下都是以第一个元素作为基数，然后先从右向左搜索，如果发现比基数小，则和基数交换，然后从左向右搜索，如果发现比基数大，则和基数交换，一直到左边大于右边，此时基数左边的都比它小，而右边的都比它大，此时基数的位置就是排好序后应该在的位置，此时基数将数组划分为左右两部分，然后可以递归采用该方法进行。

代码实例如下：

public class QuickSort {
    
    	public static void main(String[] args) {
    		int[] arr = { 12, 34, 3, 56, 7, 98, 45, 39 };
    		quickSort(arr);
    		//冒泡排序算法
    		for (int i = 0; i < arr.length - 1; 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;
    				}
    			}
    		}
    		System.out.println();
    		System.out.println("排序后的数组为：");
    		for (int num : arr) 
    			System.out.print(num + " ");
    		
    	}
    
    	/**
    	 * 快速排序算法
    	 * @param arr
    	 * @param low
    	 * @param high
    	 */
    	public static void quickSort(int[] arr, int low, int high) {
    
    		if (low > high)
    			return;
    		int i = low, j = high, index = arr[i]; // 取最左边的数为基准数
    		while (i < j) { // i==j 时 跳出循环
    			while (i < j && arr[j] >= index) // 向左寻找第一个小于index的数
    				j--;
    			if (i < j)
    				arr[i++] = arr[j];// 将arr[j]填入到arr[i],并将I向右移动一位
    			while (i < j && arr[i] < index) // 向右寻找第一个大于index的数
    				i++;
    			if (i < j)
    				arr[j--] = arr[i]; // 将arr[i]填入到arr[j],并将j向左移动一位
    		}
    		arr[i] = index;// 将基准数填入最后的坑
    		quickSort(arr, low, i - 1);// 递归调用分治
    		quickSort(arr, i + 1, high);// 递归调用分治
    		System.out.println("排序后的数组为：");
    		for (int k = 0; k < arr.length; k++) {
    			System.out.print(arr[k]+ " ");
    		}
    	}
    	public static void quickSort(int[] arr) {
    		if (arr.length == 0) 
    			return;
    		quickSort(arr, 0, arr.length - 1);
    	}
    }