快速排序法(思想及代码实现)

约定不等于承诺〃 2023-07-15 13:06 85阅读 0赞

### 快速排序思想: ###

快速排序是对冒泡排序的一种改进，基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对着两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。  
下图所示的是按照最后一个数据作为中间数，然后将整个数组分割成两个部分，代码所示的内容是取数据的中间数作为分界，然后分割成两部分。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTE1MTk2MA_size_16_color_FFFFFF_t_70]

public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		int[] arr = { -4,10,0,20,-20,1};
    		quickSort(arr, 0, arr.length-1);
    		System.out.println("排序后的数组为："+Arrays.toString(arr));
    
    	}
    	
    	public static void quickSort(int[] arr,int left,int right) { 
    		int l = left;//最左边下标
    		int r = right;//最右边下标
    		int pivot = arr[(left+right)/2];//定义中间值
    		int temp = 0; //临时变量 交换时使用
    		//while的目的是 将比pivot小的值放在左边 大的值放在右边
    		while(l<r) { 
    			//在pivot的左边一直找 找到大于等于pivot的值 才退出
    			while(arr[l] < pivot) { 
    				l++;
    			}
    			//在pivot的右边一直找 知道小于等于pivot的值 才退出
    			while(arr[r] > pivot) { 
    				r--;
    			}
    			//如果l大于等于r 说明pivot两边的值 已经按照我们需要的顺序排好了
    			if(l >= r) { 
    				break;
    			}
    			
    			//交换位置
    			temp = arr[l];
    			arr[l] = arr[r];
    			arr[r] = temp;
    			
    			//如果交换完成后 发现arr[l] == pivot 就让r-- 前移
    			if(arr[l] == pivot) { 
    				r--;
    			}
    			//如果交换完成后 arr[r] == pivot 就让l++ 后移
    			if(arr[r] == pivot) { 
    				l++;
    			}
    		}
    		
    		//如果l==r 就l++ r-- 否则会死循环 栈溢出
    		if(l == r) { 
    			l++;
    			r--;
    		}
    		
    		//向左递归
    		if(left < r) { 
    			quickSort(arr, left, r);
    		}
    		//向右递归
    		if(right > l) { 
    			quickSort(arr, l, right);
    		}
    	}

### [冒泡排序][Link 1] ###

### [插入排序][Link 2] ###

### [选择排序][Link 3] ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTE1MTk2MA_size_16_color_FFFFFF_t_70]: /images/20230528/92491bc4339b4211b374b6a014dcb162.png
[Link 1]: https://blog.csdn.net/weixin_45151960/article/details/104761269
[Link 2]: https://blog.csdn.net/weixin_45151960/article/details/104911052
[Link 3]: https://blog.csdn.net/weixin_45151960/article/details/104762648