算法:划分

划分

是快速排序的根本机制。
原理-把数组分为两组，使所有的值大于特定值的数据项的在一组，所有小于特定值的在一组。

SortUtils.java 主要完成换位和打印任务，在之后的简单排序中都会用此工具类

public class SortUtils {
	/**
	 * @param array=数组
	 * @param index=当前位置
	 * @param next=下一个位置
	 */
	public static void swap(int[] array,int index,int next){
		int tmp=array[index];
		array[index]=array[next];
		array[next]=tmp;
	}
	
	/**
	 * @param array=要打印的数组
	 */
	public static void display(int[] array){
		for(int i=0;i<array.length;i++){
			System.out.print(" "+array[i]);
		}
	}
}

Partition.java 具体实现

public class Partition {
	public static int array[]={1,222,33,45, 5, 2,332,44,87,1,2,0,33,55, 3,4};
	
	public static void sort(int minIndex,int maxIndex,int pivot){
		int leftPar=minIndex-1,rightPar=maxIndex+1;	//1
		
		while(true){	//2
			while(leftPar<maxIndex && array[++leftPar]<pivot);	//3
			
			while(rightPar>minIndex && array[--rightPar]>pivot);	//4
			
			if(leftPar>=rightPar){	//5
				break;
			}else{
				SortUtils.swap(leftPar,rightPar);	//6
			}
		}
	}
	
	public static void main(String[] args) {
		int pivot=40;//特定值
		//传入最左索引位置，和最右索引位置
		sort(0,array.length-1,pivot);
		
		SortUtils.display(array);//打印排序好的数据
	}
}

输出：1 4 33 3 5 2 33 0 2 1 87 44 332 55 45 222

说明

• 1.这里把leftPar变为小于0,rightPar变为大于总长度的原因是为了在位置3和位置4那里做++和- -操作
• 2.一直执行到最左索引和最右端索引重合或者大于最右端索引
• 3.左索引小于最大索引并且值小于特定值时一直向右比较大小
• 4.右索引大于数组最小索引并且大于特定值时一直向左比较大小
• 5.两端索引重合或者左大于右时跳出循环
• 6.交换位置

注:该内容为Java数据结构和算法读后学习感悟

其他相关文章

递归-归并排序

高级排序2-快速排序

高级排序1-希尔排序

简单排序3-插入排序

简单排序2-选择排序

简单排序1-冒泡排序

赏

谢谢你的激励

微信