设置两个变量i,j,排序开始的时候,i=0,j=length-1.
以第i个数组元素作为关键数据,赋值给key,用于比较。
从j开始向前搜索,即由后向前搜索(j--),找到第一个小于key的值[j],将[j]和位置的值进行互换。
从i开始向后搜索,即有开始向后搜索(i++),找到第一个比key小的值,将和[j]位置的值进行互换。
直到i>j循环结束。
对左侧(0,i-1)进行循环排序。
对左侧(j+1,length-1)进行循环排序。
- package com.demo.test;
- /**
- * @author 史云龙
- * 完成数组的快速排序
- * 数组【100,40,60,87,34,11,56,0】
- *快速排序:
- *从小到大排列
- */
- public class QuickSort {
-
- /**
- * @param args
- * 主函数
- */
- public static void main(String[] args) {
-
- int[] array = {100,40,60,87,34,11,56,0};
- sop("未进行快速排序的数组:");
- print(array);
- sop("已经进行快速排序的数组:");
- sort(array,0,array.length-1);
- print(array);
- }
-
- /**
- * @param array【需要排序的数组】
- * @param low【最低位】
- * @param high【最高位】
- * 快速排序[从小到大排序]
- * 算法说明:
- * 1、设置两个变量,low,high,初始排序时,low=0,high=array.length-1;
- * 第6步中,由于需要对分成的两部分数组继续进行排序,
- * 需要定义两个变化的值来分别初始low和high,这里定义为l、h;
- * 2、以第l个数组元素作为关键数据,赋值给key,即key=array[l]
- * 3、从h开始向前搜索,即由后向前搜索,找到第一个小于key的值array[h],
- * 将array[h]和array[l]互换,此后key为array[h]
- * 4、从l开始向后搜索,即由前向后搜索,找到第一个大于key的值array[l],
- * 将array[l]和array[h]互换,此后key为array[l]
- * 5、第一次排序结束后,如果l<h,则重复第3、4两步。
- * 6、如果l>h是排序结束,左侧即【low----l】不一定是符合顺序的,则对左侧排序。
- * 同时右侧【h----high】也不一定是符合顺序的,则对左侧进行排序的
- * 由于此时l>=h,对左侧排序时将l进行-1,
- * 对右侧进行排序时,将h进行+1,保证不会重复。
- * (1)l>h即l=h+1,不可能有其他情况,因为l=h+1时,循环已经结束。
- * 从新开始的排序的两段数组顺序可以看做为【low-h】【l-high】,完全包含这个数组。
- * (2)l=h,
- * 从新开始的排序的两段数组顺序可以看做为【low-l-1】【l=h】【h+1-high】,完全包含这个数组。
- * 此时array[l]==array[h]大于左侧的数据,小于右侧的数据,可以不用重新排序。
- *
- *
- */
- public static void sort(int[] array ,int low,int high){
- //如果最小位置大于最大位置,直接返回。
- if(low>=high)
- return;
- if((high-low)==1){
- if(array[low]>array[high]){
- swap(array,low,high);
- }
- return;
- }
- //默认排序的KEY值
- int key = array[low];
- //将最低值赋给一个变量,用于一次排序后进行后续排序分组
- int l = low;
- //将最高值赋给一个变量,作用同上
- int h=high;
- //如果l<h,则一直进行循环
- while(l<h){
- //从最后向前找,找到比key小的第一个数
- //如果l<h,且key比array[h]小,则一直循环
- //直到h小于等于l或此时h处的值比key小,则结束循环
- //找到比key小的值向前移动
- while(l<h&&key<array[h])
- h--;
- /*
- 与上述两行代码相同
- while(l<h){
- if(array[h]<key)
- break;
- h--;
- }
- */
- //交换l和h处位置的数据,key则是array[l],交换,
- //然后key就和array[h]相等,及此时key变换为array[h]
- //交换的目的是将小点的数向前方移动
- swap(array,l,h);
- //从前向后找,找到比key(即array[h])大的数
- //如果l<h,且key(array[h])比array[l]大,则一直循环
- //直到l大于等于h或此时l出的值比key大,则结束循环
- //找到比key大的值向后移动
- while(l<h&&key>array[l]){
- l++;
- }
- /*
- 与上述两行代码相同
- while(l<h){
- if(array[l]>key)
- break;
- l++;
- }
- */
- //交换l和h处位置的数据,key则是array[h],交换,
- //然后key就和array[l]相等,及此时key变换为array[l]
- //交换的目的是将小点的数向前方移动
- swap(array,l,h);
- }
- //对数组的两部分继续排序
- sort(array,low,l-1);
- sort(array,h+1,high);
- }
- /**
- * @param b【传入数组并进行打印】
- */
- public static void print(int[] b){
- for (int i=0;i<b.length;i++){
- sop(b[i]);
- if(i==b.length-1){
- sop("\n");
- }else{
- sop(" , ");
- }
- }
-
- }
- /**
- * @param array
- * @param i
- * @param j
- * 将符合条件的数组数据交换位置
- */
- public static void swap(int[] array,int i,int j){
- int temp = array[i];
- array[i]=array[j];
- array[j]=temp;
-
- }
- /**
- * @param obj[将obj输出]
- */
- public static void sop(Object obj){
- System.out.print(obj);
- }
- }
复制代码
|