排序算法——快速排序

你的名字 2022-11-20 08:04 279阅读 0赞

# 排序算法——快速排序 #

> 快速排序通过一趟排序将待排序序列分隔成独立的两部分，其中一部分序列的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。它的工作原理：设两个变量low（低）、high（高），排序开始时low=0（第一位的索引），high=length-1（最后一位的索引）。整个待排序序列中选一个基准数据，所有元素比基准数据小的摆在基准数据左边，所有比基准数据大的摆在基准数据右边。默认第一个数据为基准数据，赋值给temp，即temp=array\[low\]；再循环从右至左开始与temp对比，找到第一个小于temp的数据，从左至右开始与temp对比，找到第一个大于temp的数据，交换它们两个的位置，即z=array\[i\];y=array\[j\];array\[i\]=y;array\[j\]=z;循环多次，直到左边的索引与右边的索引相等，即i=j，索引i所在的位置就是temp（基准数据）所在的位置，再交换它们两的位置，第一趟找到基准位置，作为下一躺的分界点，然后递归调用分界点左边的序列排序和分界点右边的序列排序……

例如一组数组\{9,8,7,6,5,4,3,2,1\}使用快速排序顺序排序，基准数为9，从右至左找第一个小于9的数也就是1，从左至右到1找第一个大于9的数没有，就没有数与1交换；从右至左找到索引为8，也就是基准数9的位置，再交换索引为8（1）和基准数（9）的位置，得到数组\{1,8,7,6,5,4,3,2,9\}，第一趟完成。然后以9为下一趟的分界点，得到两个数组分别为\{1,8,7,6,5,4,3,2\}、\{\}，先对左边的数组进行下一趟排序，以1为基准数，从右至左找第一个小于1的数没有，就没有数可交换；从右至左找到索引为0，也就是基准数1的位置，交换索引为0（1）和基准数（1）的位置，得到数组\{1,8,7,6,5,4,3,2,9\}。然后以1位下一趟的分界点，得到两个数组分别为\{\}、\{8,7,6,5,4,3,2,9\}，左边为空的数组，只对右边的数据进行下一趟排序，以8为基准数，从右至左找第一个小于8的数也就是2，从左至右到2找第一个大于8的数没有，就没有数与2交换；从右至左找到索引为7，也就是基准数2的位置，再交换索引为7（2）和基准数（8）的位置，得到数组\{1,2,7,6,5,4,3,8,9\}。然后以8为下一趟的分界点，得到两个数组分别为\{1,2,7,6,5,4,3\}、\{9\}，先对左边的数组进行下一趟排序，以1为基准数，从右至左找第一个小于1的数没有，就没有数可交换；从右至左找到索引为0，也就是基准数1的位置，交换索引为0（1）和基准数（1）的位置，得到数组\{1,2,7,6,5,4,3,8,9\}。然后以1为下一趟的分界点，得到两个数组分别为\{\}、\{2,7,6,5,4,3,8,9\}，左边为空的数组，只对右边的数据进行下一趟排序，以2为基准数，从右至左找第一个小于2的数没有，就没有数可交换；从右至左找到索引为1，也就是基准数2的位置，交换索引为1（2）和基准数（2）的位置，得到数组\{1,2,7,6,5,4,3,8,9\}。然后以2为下一趟的分界点，得到两个数组分别为\{1\}、\{7,6,5,4,3,8,9\}，先对左边的数组进行下一趟排序也就是\{1,2,7,6,5,4,3,8,9\}；再对右边的数组进行下一趟排序，以7为基准数，从右至左找第一个小于7的数也就是3，从左至右到3找第一个大于7的数没有，就没有数与3交换；从右至左找到索引为6，也就是基准数7的位置，再交换索引为6（3）和基准数（7）的位置，得到数组\{1,2,3,6,5,4,7,8,9\}。然后以7为下一趟的分界点，得到两个数组分别为\{1,2,3,6,5,4\}、\{8,9\}，先对左边的数组进行下一趟排序，以1为基准数，从右至左找第一个小于1的数没有，就没有数可交换；从右至左找到索引为0，也就是基准数1的位置，交换索引为0（1）和基准数（1）的位置，得到数组\{1,2,3,6,5,4,7,8,9\}。然后以1为下一趟的分界点，得到两个数组分别为\{\}、\{2,3,6,5,4,7,8,9\}，左边为空的数组，只对右边的数据进行下一趟排序，以2为基准数，从右至左找第一个小于2的数没有，就没有数可交换；从右至左找到索引为1，也就是基准数2的位置，交换索引为1（2）和基准数（2）的位置，得到数组\{1,2,3,6,5,4,7,8,9\}。然后以2为下一趟的分界点，得到两个数组分别为\{1\}、\{3,6,5,4,7,8,9\}，先对左边的数组进行下一趟排序也就是\{1,2,7,6,5,4,3,2,8,9\}；再对右边的数组进行下一趟排序，以3为基准数，从右至左找第一个小于3的数没有，从左就没有数可交换；从右至左找到索引为2，也就是基准数3的位置，交换索引为2（3）和基准数（3）的位置，得到数组\{1,2,3,6,5,4,7,8,9\}。然后以3为下一趟的分界点，得到两个数组分别为\{1,2\}、\{6,5,4,7,8,9\}，先对左边的数组进行下一趟排序也就是\{1,2,3,6,5,4,7,8,9\}；再对右边的数组进行下一趟排序，以6位基准数，从右至左找第一个小于6的数也就是4，从左至右到4找第一个大于6的数没有，就没有数与4交换；从右至左找到索引为5，也就是基准数6的位置，再交换索引为5（4）和基准数（6）的位置，得到数组\{1,2,3,4,5,6,7,8,9\}……，把剩余未排序的半边数组排序，最终就会得到排序好的数组\{1,2,3,4,5,6,7,8,9\}。

<table> 
 <thead> 
  <tr> 
   <th>次数</th> 
   <th>小于基准数</th> 
   <th>基准数</th> 
   <th>大于基准数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>开始</td> 
   <td></td> 
   <td>9,8,7,6,5,4,3,2,1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>第一次</td> 
   <td>1,8,7,6,5,4,3,2</td> 
   <td>9</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>第二次</td> 
   <td></td> 
   <td>1</td> 
   <td>8,7,6,5,4,3,2,9</td> 
  </tr> 
  <tr> 
   <td>第三次</td> 
   <td>1,2,7,6,5,4,3</td> 
   <td>8</td> 
   <td>9</td> 
  </tr> 
  <tr> 
   <td>第四次</td> 
   <td>1</td> 
   <td>2</td> 
   <td>7,6,5,4,3,8,9</td> 
  </tr> 
  <tr> 
   <td>第五次</td> 
   <td>1,2,3,6,5,4</td> 
   <td>7</td> 
   <td>8,9</td> 
  </tr> 
  <tr> 
   <td>第六次</td> 
   <td>1,2</td> 
   <td>3</td> 
   <td>6,5,4,7,8,9</td> 
  </tr> 
  <tr> 
   <td>第七次</td> 
   <td>1,2,3,4,5</td> 
   <td>6</td> 
   <td>7,8,9</td> 
  </tr> 
  <tr> 
   <td>第八次</td> 
   <td>1,2,3</td> 
   <td>4</td> 
   <td>5,6,7,8,9</td> 
  </tr> 
  <tr> 
   <td>第九次</td> 
   <td>1,2,3,4</td> 
   <td>5</td> 
   <td>6,7,8,9</td> 
  </tr> 
 </tbody> 
</table>

###### Java代码实现： ######

public static void main(String[] args) { 
    	int[] arr = { 9,8,7,6,5,4,3,2,1};
    	quickSort(arr,0,arr.length-1);
    }
    static int t;
    public static void quickSort(int[] array,int low,int high)//快速排序
    { 
    	int i,j,temp,y,z;
    	if(low>high){ 
    		return;
    	}
    	i=low;//左边的索引
    	j=high;//右边的索引
    	//temp就是基准数
    	temp = array[low];//以最左边的数为基准数
    	while (i<j) { 
    		//先看右边，依次往左递减
    		//先从右往左找一个小于基准位的数
    		//当右边的位置所在的数>基准位的数时，继续从右往左找（同时j-1）
    		//找到后就跳出 while循环
    		while (temp<=array[j]&&i<j) { 
    			j--;
    		}
    		//再看左边，依次往右递增
    		//先从左往右找一个大于基准位的数
    		//当右边的位置所在的数<基准位的数时，继续从左往右找（同时i+1）
    		//找到后就跳出 while循环
    		while (temp>=array[i]&&i<j) { 
    			i++;
    		}
    		//如果满足条件则交换
    		if (i<j) { 
    			//z、y是临时参数，用于存放大于基准数和小于基准数所在位置的数据
    			z = array[i];
    			y = array[j];
    			//交换数据
    			array[i] = y;
    			array[j] = z;
    		}
    	}
    	//这时 跳出了 “while (i<j) {}” 循环
    	//说明 i=j 左右在同一位置
    	//最后将基准为与i和j相等位置的数字交换
    	array[low] = array[i];//或 array[low] = arr[j];
    	array[i] = temp;//或 array[j] = temp;
    	t++;
    	System.out.format("第%d趟：\t", t);
    	for (int l : array) { 
    		System.out.print(l+",");
    	}
    	System.out.println();
    	//这时基准数已经确定排序位置， 所以就不用再对它进行排序了
    	//只要用相同的方法分别处理基准数左右数组就可以了
    	//递归调用左数组
    	quickSort(array, low, j-1);
    	//递归调用右数组
    	quickSort(array, j+1, high);
    }

###### 执行结果： ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU0NzU5OQ_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU0NzU5OQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a80c4b1e2c0642acaf527279573884a5.png