方法1:
public class QuickSort {
int[] n ={45,99,69,29,28,27,26,2,10,3,24,23,9,8,25,85,33,40,78,98,54,7,69};
public static void main(String[] args) {
QuickSort q = new QuickSort();
q.out(q.n.length);
q.quickSort(0, q.n.length-1);
q.out(q.n.length);
}
/**
* 快速排序主循环体,主要利用一个可变数组list
* 把作为参考的基准数先放到list中,然后跟数组一段区间内的数
* 比较,大的放到list末尾,小的就放到这个基准数的左边
* @param i 数组区间的起始坐标
* @param j 数组区间的终止坐标
*/
public void quickSort(int i, int j){
int t = n[i]; //t 记录一个用来做参考的数
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(t);
int length = j + 1 - i; //记录i----j总共是多少个数字
int start = i++; //记录i的起始坐标
int left = 0; //给temp里面填数字时候的坐标,也就是小于t的数值的索引
int right = length -1;
/**
* 判断temp数组当前的左边left和右边坐标right是否重叠
* 如果重叠就表示区间内所有数据都按一定的顺序放到temp中
*/
while(left < right){
if(t < n[j]){
//将此数字加到末尾
temp.add(n[j]) ;
right--;
}else{
//在temp中放到t的前面
temp.add(left, n[j]);
left++;
}
if(left == right){
break;
}
if(t < n[i]){
temp.add(n[i]);
right--;
}else{
temp.add(left, n[i]);
left++;
}
i += 1;
j -= 1;
}
//到此时temp里面的顺序就排成了左边都小于t,右边都大于t
for(int k = 0; k < temp.size(); k++){
n[start + k] = temp.get(k);
}
//以t为分界线再分别对左边和右边进行划分,这样逐级进行最终将分成若干对最小的两个数值比较
//t的左边在原数组里的范围
if(left > 1){
quickSort(start, start + left -1);
}
//t的右边在原数组里的范围
if(left + 1 < length -1){
quickSort(start + left + 1, start + length -1);
}
}
public void out(int j){
for(int i = 0; i < j; i++){
System.out.print(n[i] + " ");
}
System.out.println();
}
}
分享到:
相关推荐
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
快速排序法(quick sort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。 快速排序法的基本精神是在数列中...
这是一个用Java语言实现的快速排序算法,快速排序算法是根据分冶思想去实现的。
快速排序法 C++ 初学者代码 简单的准确的
在快速排序法基础上提供了一些改进,比基本的快速排序更方便简洁
java Document 快速排序法 java Document 快速排序法 java Document 快速排序法
清楚明确的代码书写,让你轻易学懂快速排序法
使用快速排序法对一维数组进行排序,程序完全可以运行,方便大家学习
void qsort(int arr[],int left,int right) //qsort()函数实现快速排序,并且是递归调用,而且,递归调用qsort()函数本身两次,因为要对中值两边的 { //部分分别进行排序。arr是待排序的数组名,left是排序的左边界,...
直接排序法,折半插入法,希尔排序法,快速排序法(c语言实现),适合初学数据结构的同学。全部程序都在VC++6.0调试通过。
利用matlab实现的快速排序法;详细解释请看:https://blog.csdn.net/fyf18845165207/article/details/85346084 内含C++语言实现
快速排序法 程序 绝对原创 老师布置的作业 欢迎大家下载
c#中快速排序法算法代码实例,文档中的代码实测可用。
java 快速排序 折半查找的界面实现 (递归与分治法)
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为: 从数列中挑出一个元素,称为“基准”(pivot), 重新排序数列,所有比基准值小的元素摆放在基准前面...
韩顺平老师的快速排序法源代码 经本人测试 完整无误 可以直接用
一个快速排序法的例子 构建1亿的随机数,完整排序花时26秒左右
Java 冒泡法,选择法,插入法,快速排序法,实现代码。
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序
分治法的另外一种排序算法,快速排序。有注释,便于阅读,因为交换时使用的引用,暂时归为C++,C语言版稍后奉上。