package QuickSort;
import java.util.ArrayList;
public class QuickSort {
public static void main(String[] args) {
ArrayList<Integer> lists = new ArrayList<Integer>();
lists.add(5);
lists.add(2);
lists.add(6);
lists.add(1);
lists.add(7);
lists.add(3);
lists.add(4);
//System.out.println(isOdd(3));
//System.out.println(isOdd(4));
System.out.println(lists);
//System.out.println(getMiddle(lists));
//System.out.println(lists.indexOf(getMiddle(lists)));
System.out.println(sort(lists));
}
//
public static boolean isOdd(int i) {
if(i % 2 == 0) {
return false;
}
else {
return true;
}
}
//
private static Integer getMiddle(ArrayList<Integer> array) {
if (isOdd(array.size())) {
return array.get(array.size()/2);
}
else {
return array.get(array.size()/2);
}
}
private static ArrayList<Integer> sort(ArrayList<Integer> array) {
int mid = getMiddle(array);
int midIndex = array.indexOf(mid);
int i = 0;
int j = array.size()-1;
int temp = array.get(0);
while(i!=midIndex || j !=midIndex) {
if(array.get(i) < mid) {
i++;
}
else {
if (array.get(j)>mid) {
j--;
}
else {
array.set(i, array.get(j));
array.set(j, temp);
i++;
j--;
temp = array.get(i);
}
}
}
return array;
}
}
一、交换部分错了
temp = array.get(i);
array.set(i, array.get(j));
array.set(j, temp);
i++;
j--;
二、分成大小两部分之后的递归呢？
看你的代码不像是快速排序啊。
快速排序的java实现参考:http://www.cnblogs.com/vanezkw/archive/2012/06/21/2557685.html
http://blog.csdn.net/strutce/article/details/47784735
public void sort(int arr[],int low,int high)
{
int l=low;
int h=high;
int povit=arr[low];
while(l {
while(l=povit)
h--;
if(l<h){
int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
l++;
}
while(l<h&&arr[l]<=povit)
l++;
if(l int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
h--;
}
}
print(arr);
System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n");
if(l>low)
sort(arr,low,l-1);
if(h<high)
sort(arr,l+1,high);
}
}
快排是取一个数，将小于它的放到左边，大于它的放到右边，然后做递归，你这段代码，完全看不出来你在做快排
public void sort(int arr[],int low,int high)
{
int l=low;
int h=high;
int povit=arr[low];
while(l {
while(l=povit)
h--;
if(l<h){
int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
l++;
}
while(l<h&&arr[l]<=povit)
l++;
if(l int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
h--;
}
}
print(arr);
System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n");
if(l>low)sort(arr,low,l-1);
if(h<high)sort(arr,l+1,high);
}
}
public class quickSort {
public static void main(String[] args){
int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
quickSort qs=new quickSort();
qs.quick(a);
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
public int getMiddle(int[] list, int low, int high) {
int tmp = list[low];
while (low < high) {
while (low < high && list[high] >= tmp) {
high--;
}
list[low] = list[high];
while (low < high && list[low] <= tmp) {
low++;
}
list[high] = list[low];
}
list[low] = tmp;
return low;
}
public void _quickSort(int[] list, int low, int high) {
if (low < high) {
int middle = getMiddle(list, low, high);
_quickSort(list, low, middle - 1);
_quickSort(list, middle + 1, high);
}
}
public void quick(int[] a2) {
if (a2.length > 0) {
_quickSort(a2, 0, a2.length - 1);
}
}
}
这个是用数组做的，你参考一下
import java.util.Scanner;
public class quicksort {
public static void quicksort(int a[],int left,int right){
if(left<right){
int i=left,j=right;
int vot=a[i];
while(i!=j){
while(i<j&&vot<=a[j])
j--;
if(i<j)
a[i++]=a[j];
while(i<j&&vot>=a[i])
i++;
if(i<j)
a[j--]=a[i];
}
a[i]=vot;
quicksort(a,left,j-1);
quicksort(a,i+1,right);
}
}
public static void main(String[] args) {
Scanner n1=new Scanner(System.in);
int s=n1.nextInt();
int a[]=new int[s];
for(int i=0;i<a.length;i++){
a[i]=n1.nextInt();
}
quicksort(a, 0, a.length-1);
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
}
}
http://blog.csdn.net/williamfan21c/article/details/47630493
/*对顺序表L.r[low..high]的元素进行一趟排序，使枢轴前面的元素关键字小于
枢轴元素的关键字，枢轴后面的元素关键字大于等于枢轴元素的关键字，并返回枢轴位置*/
int Partition(SqList *L,int low,int high){
DataType t;
KeyType pivotkey;
pivotkey=(*L).data[low].key; //将表的第一个元素作为枢轴元素
t=(*L).data[low];
while(low while(low=pivotkey) //从表的末端向前扫描
high--;
if(low<high){ //将当前high指向的元素保存在low位置
(*L).data[low]=(*L).data[high];
low++;
}
while(low<high&&(*L).data[low].key<=pivotkey) //从表的始端向后扫描
low++;
if(low<high){ //将当前low指向的元素保存在high位置
(*L).data[high]=(*L).data[low];
high--;
}
}
(*L).data[low]=t; //将枢轴元素保存在low=high的位置
return low; //返回枢轴所在位置
}
//
void DispList2(SqList L,int pivot,int count){
int i;
printf("第%d趟排序结果:[",count);
for(i=1;i<pivot;i++)
printf("%-4d",L.data[i].key);
printf("]");
printf("%3d ",L.data[pivot].key);
printf("[");
for(i=pivot+1;i<=L.length;i++)
printf("%-4d",L.data[i].key);
printf("]");
printf("\n");
}
//对顺序表L进行快速排序
void QSort(SqList *L,int low,int high){
int pivot;
static int count=1;
if(low<high){ //如果元素序列的长度大于1
pivot=Partition(L,low,high); //将待排序序列L.r[low..high]划分为两部分
DispList2(*L,pivot,count); //输出每次划分的结果
count++;
QSort(L,low,pivot-1); //对左边的子表进行递归排序，pivot是枢轴位置
QSort(L,pivot+1,high); //对右边的子表进行递归排序
}
}
//对顺序表L作快速排序
void QuickSort(SqList *L){
QSort(L,1,(*L).length);
}
http://blog.csdn.net/havedream_one/article/details/46315305
各种排序算法都有，参考https://www.xlongwei.com/detail/15032520