java排序算法：冒泡排序、插入排序、选择排序、快速排序

落日映苍穹つ 2022-05-09 15:10 351阅读 0赞

#### 1. 冒泡排序 ####

核心思想:相邻的元素进行比较，满足条件就进行交换。如果一趟排序中没有出现元素交换则排序完成。
       a.比较相邻位置的两个元素，若第一个元素(左边)比第二个元素(右边)大，则交换元素的位置。
       b.从开始的第一对元素一直到结尾的最后一对，经过这一轮，排在最后的元素将是这组元素的最大值。
       c.重复步骤b持续对越来越少的元素进行两两比较，直到所有元素处理完毕为止。
         (直到任何两个相邻位置的元素都不需要发生交换为止)

算法实现

public static void sort(int[] arr){
    	int x;
    	for(int i = 1;i<arr.length;i++){
    		//内层循环控制比较次数，相邻元素比较，如果这一趟排序没有元素交换则终止外循环。
    		boolean flag = true;
    		for(int j = 0;j<arr.length-i;j++){
    			if(arr[j]>arr[j+1]){
    				x = arr[j];
    				arr[j] = arr[j+1];
    				arr[j+1] = x;
    				flag = false;
    			}
    			if(flag)
    				break;
    		}
    	}
    }

#### 2. 插入排序 ####

算法流程
       a.从第一个元素起，认定该元素已经有序。
       b.取出下一个元素，让取出的元素与左边的有序数列从右向左依次比较大小。
       c.若取出的元素小于左边的元素，则将左边的元素右移，也就是赋值到下一个元素的位置。
       d.若取出的元素大于等于左边的元素，则将取出的元素插入到左边元素的右边。
       e.重复步骤b，直到处理完毕所有的元素为止。

#### 3. 选择排序 ####

算法流程
       a.从第一个元素起依次取出，并假定该元素是这组元素中的最小值，使用min变量记录。
       b.使用min记录的最小值与后续元素依次比较大小。
       c.若后续元素中找到了比min记录的最小值还小的元素，则使用min重新记录该元素下标。
       d.直到min记录的最小值与后续所有元素都比较完毕时，交换min记录的最小值和最开始假定的最小值。
       e.重复步骤a,直到处理完毕所有元素为止。

#### 4. 快速排序 ####

算法流程
       a.计算出中间元素的下标，让中间元素作为基准值，单独保存起来。
       b.分别让左右两边的元素与基准值比较大小，将所有比基准值小的元素都放在基准值的左边，将所有大于等于基准值的元素都放在基准值的右边，这个过程叫分组。
       c.直到左右两边的元素下标重合时，将基准值放到重合的位置，此时分组完成。
       d.分别对左右两边的分组重复上述过程，因此使用递归实现。

算法实现

public static void quick(int[] arr, int left, int right){
    	//1.计算中间元素的下标，让中间元素作为基准值单独保存起来
    	int p = (left + right) / 2;
    	int pivot = arr[p];
    	//2.分别用左右两边的元素与基准值进行比较，将所有比基准值小的元素都放在基准值的左边，大于等于放右边
    	int i = left;	//为了使left，right保持不动，因传参时需要
    	int j = right;
    	for( ; i < j; ){	//直到重合时结束
    		//用左边的元素与基准值比较大小，若左边有元素且小于基准值，则下标移动，让下一元素与基准值比较
    		while(i < p && arr[i] < pivot){
    			i++;
    		}
    		//直到左边有元素，但左边元素不再小于基准值时，将左边元素赋值到p指向的位置，
    		//p指向该元素原来的位置
    		if(i < p){
    			arr[p] = arr[i];
    			p = i;
    		}
    		//----------------------------右侧----------------------------
    		while(j > p && arr[j] >= pivot){	//与左侧对应，左侧为<右侧就得加=
    			j--;
    		}
    		if(j > p){
    			arr[p] = arr[j];
    			p = j;
    		}
    	}
    	//3.直到左右两边的元素下标重合时，将单独保存的基准值放到重合的位置
    	arr[p] = pivot;
    	//4.分别对左右两边的分组进行再次分组，使用递归实现
    	if(p - left > 1){		//当左右两侧的元素个数为0，或1时不用比较
    		quick(arr, left, p-1);
    	}
    	if(right - p > 1){
    		quick(arr, p+1, right);
    	}
    }