第二十六篇 快速排序
栏目分类:java教程 发布日期:2019-09-21 浏览次数:次
第18章-快速排序
通过上一章的学习我们已经了解了算法的一些基础和学习了冒泡排序。
这一节我们就来学习快速排序。话不多说直接上代码:
public class QuickSort {
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i!=j) {
//先看右边,依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边,依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
public static void main(String[] args){
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
上面的方法是利用了递归的特点,而下面这段代码则是没有利用递归,我们也来看看:
public static int quicksort(int[] array,int low,int high){
int point = array[low];
while(low < high){
while(low < high && array[high] >= point){
high--;
}
if(low >= high){
break;
}else{
array[low] = array[high];
}
while(low < high && array[low] <= point){
low++;
}
if(low >= high){
break;
}else{
array[high] = array[low];
}
}
array[low] = point;
return low;
}
public static void Quicks(int[] array){
int[] stack = new int[array.length];
int top = 0;
int low = 0;
int high = array.length-1;
int par = quicksort(array,low,high);
//入栈
if(par > low+1){
stack[top++] = low;
stack[top++] = par-1;
}
if(par < high-1){
stack[top++] = par+1;
stack[top++] = high;
}
//出栈
while(top > 0){
high = stack[--top];
low = stack[--top];
par = quicksort(array,low,high);
if(par > low+1){
stack[top++] = low;
stack[top++] = par-1;
}
if(par < high-1){
stack[top++] = par+1;
stack[top++] = high;
}
}
}
同学们也可以自己对算法进行优化出处理。
通过上一章的学习我们已经了解了算法的一些基础和学习了冒泡排序。
这一节我们就来学习快速排序。话不多说直接上代码:
public class QuickSort {
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i!=j) {
//先看右边,依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边,依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
public static void main(String[] args){
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
上面的方法是利用了递归的特点,而下面这段代码则是没有利用递归,我们也来看看:
public static int quicksort(int[] array,int low,int high){
int point = array[low];
while(low < high){
while(low < high && array[high] >= point){
high--;
}
if(low >= high){
break;
}else{
array[low] = array[high];
}
while(low < high && array[low] <= point){
low++;
}
if(low >= high){
break;
}else{
array[high] = array[low];
}
}
array[low] = point;
return low;
}
public static void Quicks(int[] array){
int[] stack = new int[array.length];
int top = 0;
int low = 0;
int high = array.length-1;
int par = quicksort(array,low,high);
//入栈
if(par > low+1){
stack[top++] = low;
stack[top++] = par-1;
}
if(par < high-1){
stack[top++] = par+1;
stack[top++] = high;
}
//出栈
while(top > 0){
high = stack[--top];
low = stack[--top];
par = quicksort(array,low,high);
if(par > low+1){
stack[top++] = low;
stack[top++] = par-1;
}
if(par < high-1){
stack[top++] = par+1;
stack[top++] = high;
}
}
}
同学们也可以自己对算法进行优化出处理。
本文由IT教学网整理发布,转载请注明出处:http://www.itjx.com/jiaocheng/java/468.html