Quick sort algorithm is quite like the merge sort, cause both of them use the idea of divide-and-conquer, but be aware, quick sort doesn't conquer it subproblems, cause when the problem is divided into small enough (only 1 element in the sub array), the
whole array have already been sorted.
The worst case running time of quick sort is O(n^2), this can happen when the array is already sorted, so the total running time is T(n) = T(n-1) + /theta(n), and we can have T(n) =O(n^2). To avoid such case, we can randomly pick one as the pivot and
swap it with the last element in the array, and the running time will be O(n lgn) because T(n) = 2 T(n/2) +/theta(n) .
public class QuickSortRecursive {
public static void main(String[] args) {
QuickSortRecursive qsr = new QuickSortRecursive();
int[] array = {0, -1};
qsr.quickSort(array, 0, array.length - 1);
for (int i : array) {
System.out.print(i + " ");
}
}
public void quickSort(int[] array, int begin, int end) {
if (begin < end) {
//get the pivot position, and divide.
int partitionPosition = partition(array, begin, end);
// the left part of the array.
quickSort(array, begin, partitionPosition - 1);
// the right part of the array.
quickSort(array, partitionPosition + 1, end);
}
}
public int partition(int[] array, int begin, int end) {
Random rd = new Random();
int tempPivot = rd.nextInt(end - begin + 1) + begin;
swap(tempPivot, end, array);
int startPoint = begin;
for (int j = begin; j < end; j++) {
if (array[j] < array[end]) {
swap(startPoint, j, array);
startPoint++;
}
}
swap(end, startPoint, array);
return startPoint;
}
private void swap(int p1, int p2, int[] array)
{
int temp = array[p1];
array[p1] = array[p2];
array[p2] = temp;
}
}
The non-recursive quicksort stores the pair of left index and right index in the stack, and each time the array is divided, the new pair of left and right indices are stored. If the left index is larger than or equal to the right index, we will not store that
pair of indices because the number of element in that segment should be only one.
public class QuickSortNonRecursive {
public static void main(String[] args) {
QuickSortNonRecursive qsnr = new QuickSortNonRecursive();
int[] array = {0, 2, -11, 2, 18, 99, 3, 5, 11, 22, 9, 100};
qsnr.quicksort(array);
for (int i : array) {
System.out.print(i + " ");
}
}
public void quicksort(int[] array) {
if (array == null || array.length == 1) return;
//store the pair of start point and end point
Stack<Integer> s = new Stack<Integer>();
s.push(0);
s.push(array.length - 1);
while (!s.empty()) {
int right = s.pop();
int left = s.pop();
//if right <= left, the subarray only contains
// one or null element
if (right <= left) continue;
int i = partition(array, left, right);
//add the the pair of start point and end point
//to stack
if (left < i - 1) {
s.push(left);
s.push(i - 1);
}
if (i + 1 < right) {
s.push(i+1);
s.push(right);
}
}
}
public int partition (int[] array, int left, int right) {
int position = left;
int pointer = left;
while (pointer < right) {
if (array[pointer] < array[right]) {
swap(array, pointer, position);
position++;
}
pointer++;
}
swap(array, position, right);
return position;
}
public void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
转载请注明出处:http://blog.csdn.net/beiyeqingteng
分享到:
相关推荐
快速排序算法设计与分析总结 二叉树与树的转换前序、后序的递归、非递归算法,层次序的非递归算法的实现 二叉树与树的转换前序、后序的递归、非递归算法,层次序的非递归算法的实现,应包含建树的实现 实现树与...
详细解释了快速排序的java实现.里面有代码,还有注释说明
用非递归算法实现quicksort快速排序,高效
用C实现了快速排序的非递归算法. int quickpass ( sqlist &R, int low, int high ) { ... } void quicksort ( sqlist &r, int low, int high ) { ... }
快速排序一般用的是递归算法,利用系统的提供的栈结构,而此非递归算法没有利用栈,巧妙完成了排序,并提供人机交互界面
希尔排序,冒泡排序、快速排序递归排序,快速排序非递归排序,快速排序改进算法
用栈实现的快速排序,避免了原来的递归算法
常见的四种排序算法是:简单选择排序、冒泡排序、插入排序和快速排序。其中的快速排序的优势明显,一般使用递归方式实现,但遇到数据量大的情况则无法适用。实际工程中一般使用“非递归”方式实现。实际工程中一般...
常见的四种排序算法是:简单选择排序、冒泡排序、插入排序和快速排序。其中的快速排序的优势明显,一般使用递归方式实现,但遇到数据量大的情况则无法适用。实际工程中一般使用“非递归”方式实现。本文搜集发布四种...
文章目录1. 基本思想2. 代码实现2.1 递归实现2.2 优化—非递归实现3. 性能分析 1. 基本思想 在数列排序中,如果只有一个数,那么它本身就是有序的;如果只有两个数,那么一次... 快速排序多种递归、非递归实现及性能
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
C语言实现常见排序算法。编译环境:VS2010。 包括: 冒泡排序 快速排序 直接插入排序 Shell排序 直接选择排序 堆排序 归并排序(递归和非递归两种) 桶式排序 基数排序:顺序和静态队列两种方法 索引排序(采用简单...
各种排序算法,希尔排序,递归的快速排序, 非递归的快速排序,基数排序 ,堆排序,归并排序 的代码实现。 文件类型为.c文件
各种基本排序算法:冒泡排序、计数排序、堆排序、插入排序、归并排序递归版与非递归版、快速排序递归版与非递归版、选择排序、随机选择递归版与非递归版。
快速排序、堆排序、二路归并排序(递归和非递归实现)、多路归并排序
主要包括冒泡排序(两种思路实现)、冒泡排序的改进算法、选择排序法、插入排序法(两种实现方式)、快速排序法、归并排序法 (递归实现和非递归实现),该资料为本人亲自整理,且代码完整、注释全面!
冒泡,快速排序算法比较试分别实现冒泡排序和非递归形式的快速排序算法,并通过随机数据比较两种排序算法中关键字的比较次数和移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少...
各种排序算法——直接顺序排序,希尔排序,起泡排序,快速排序,简单选择排序,筛选法调整堆,堆排序,一次归并,一趟归并,归并排序的非递归算法……
(4) 递归和非递归的归并排序。 2. 产生不同规模和分布的数据,以 Excel 生成算法执行时间 T(n)关于输入规模 n 的曲线的形式,给出输入规模和分布对排序方法运行时间变化趋势的影响, 并与理论分析结果比较。 3. ...