黑马程序员技术交流社区

标题: 请问快速排序是不是在，冒泡排序的基础上改进的？ [打印本页]

作者: 陈红建 时间: 2012-7-30 18:29
标题: 请问快速排序是不是在，冒泡排序的基础上改进的？
能不能帮我写一个快速排序数据的例子？我看过一些其他的例子，感觉好乱啊。谁有思路比较清晰一点的例子啊！

作者: 刘海源 时间: 2012-7-30 19:26
冒泡排序:相邻两个元素比较，

public static void main(String[] args)
{
 int[] arr={57,23,19,89,66,74};
 for(int x=0; x<arr.length-1; x++)
 {
for(int y=0; y<arr.length-1-x; y++)
{
if(arr[y]>arr[y+1])
{
 int temp = arr[y];
 arr[y] = arr[y+1];
 arr[y+1] = temp;
 swap(arr,y,y+1);
}
}
 }
 for(int x=0; x<arr.length-1; x++)
 {
 System.out.println(arr[x]);
 }

}

作者: 金龙 时间: 2012-7-30 20:36
没看懂你的意思，如果你是想要知道高效的排序方式，插入排序倒是挺高效的，以下是我写的插入排序 public static void insertSort(int[] arr)
{
for (int x =1;x<arr.length ;x++ )
{
int temp = arr[x];//定义一个临时变量去接收每次需要比较的数据
int y = x-1; //定义一个变量，记录前一个角标位。
while (temp<arr[y]) //开始比较，这是升序排序，如果要降序，可以把"<"改成">"
{
arr[y+1]=arr[y]; //如果这个数比前一个小，那么前一个数的角标位后移。
y--; //比较后，y--，意为再和前一位角标去比

if (y==-1) //如果y自减到-1，结束本次比较
{
break;
}
}
arr[y+1]=temp;//此时y自减的数字的后一位则是temp应该在的位置
}
}

作者: 郑正华 时间: 2012-7-30 20:53
本帖最后由郑正华于 2012-7-30 21:00 编辑

快速排序是对冒泡排序的一种改进，它的基本思想就是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对两部分数据分别进行快速排序，整个排序过程可以递归进行。这个概念什么的你可以参考下百度百科~~
在这里我给你举个例子说下一趟排序算法，给你点思路，
int arr[] = {5,2,8,6,7,52,4,11};
1，设置两个变量，i = 0 ;j = arr.length-1;
2，把第一个数组元素5作为关键数据赋值给k，即k =arr[0];
3，从数组的最后一个元素开始向前搜索，j--，找到第一个小于k的值arr[j]，然后arr[j]和arr交换，
数组变为：4 2 8 6 7 52 5 11
4，从数组第一个元素开始向后搜索，i++，找到第一个大于k的值arr，并做交换处理，就是arr和arr[j]交换；
数组变为：4 2 5 6 7 52 8 11
5，重复3,4,5步骤，直到 i = j，注意关键数据k值永远不变就行。经过一趟快速排序后你就会发现关键值k的左边都比k小，k的右边的数值都比k要大。
具体代码我也没时间写啦，给你提供一个网址，这上面有个例子，就是下面的代码，你不妨试试，研究研究：
http://www.oschina.net/code/snippet_186712_6364

public class QSort
{
/**
* @param args
*/
public static void main(String[] args)
{
// TODO 自动生成方法存根
quicksort qs = new quicksort();
int data[] = {44,22,2,32,54,22,88,77,99,11};
qs.data = data;
qs.sort(0, qs.data.length-1);
qs.display();
}
}
class quicksort
{
public int data[];
private int partition(int sortArray[],int low,int hight)
{
int key = sortArray[low];
while(low<hight)
{
while(low<hight && sortArray[hight]>=key)
hight--;
sortArray[low] = sortArray[hight];
while(low<hight && sortArray[low]<=key)
low++;
sortArray[hight] = sortArray[low];
}
sortArray[low] = key;
return low;
}
public void sort(int low,int hight)
{
if(low<hight)
{
int result = partition(data,low,hight);
sort(low,result-1);
sort(result+1,hight);
}
}
public void display()
{
for(int i=0;i<data.length;i++)
{
System.out.print(data[i]);
System.out.print(" ");
}
}
}

复制代码

作者: 叶久瑞 时间: 2012-7-30 22:56
毕老师讲了一个很好的方法，可以很好的区分选择排序跟冒泡排序，我回来总结了一下，又加上了一些思路，这主要就是思路。可以使用打印倒三角形的方法来记住这两种排序
思路：大圈套小圈的思想。通过排序分析后，会发现，就是和这个原理很像。
我很想发一张图片上来，但是就是发不了，很纠结，那好吧，只能把代码发到下面了，里面有思路：
———————————————————————————————————————————————————————————————————
**************************************************************************************************************************
1、使用选择排序法对数组进行排序？？？？？？？？？？？？？？？？？
**************************************************************************************************************************
//选择排序

/*思路：1.明确最终结果是是什么。最终结果是对一个数组进行排序，他们都是整型的int类型的。
2.明确未知变量，数组中的下角标比较未知，这两个数字都是未知的*/

public static void selectSort(int [] arr)
{
for (int x=0;x<arr.length-1 ; x++)
{
for(int y=x+1;y<arr.length;y++)
{
if (arr[x]>arr[y]) //假如把这个>号换个方向，那么它的排序后的顺序就换了。
{
swap(arr,x,y);
}
}
}
}

/*定义一个输出语句*/

public static void sop(String str)
{
System.out.println(str);
}

/*对数组中的位置进行置换*/

public static void swap(int []arr,int a,int b)
{
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;

}

/*定义一个功能先对函数进行遍历，先输出原始函数，然后再输出排序后的函数*/
public static void printArry(int [] arr)
{
for (int x=0;x<arr.length ;x++ )
{
if (x!=arr.length-1)
System.out.print(arr[x]+".");
else
System.out.println(arr[x]);
}

}

**************************************************************************************************************************
2.使用冒泡排序法对数组进行排序？？？？？？？？？？？？？？？？？
**************************************************************************************************************************

主函数调用如下：
int [] arr={36,23,55,65,23,45,65,32};
sop("排序前");
printArry(arr);
sop("排序后");
bubbleSort(arr);
printArry(arr);

程序如下：
public static void bubbleSort(int[] arr)
{
for (int x=0;x<arr.length-1 ;x++ )
{
for (int y=0;y<arr.length-1-x ;y++ )
{
if (arr[y]<arr[y+1])
{
swap(arr,y,y+1);
}

}
}
}
**************************************************************************************************************************
3.对数组中的元素进行反转？？？？？？？？？？？？？？？？？
**************************************************************************************************************************

/*
对给定的数组中的元素进行反转。
{6,9,12,44,21};-->
{21,44,12,9,6};

思路：
1，反转其实就是头尾角标的元素进行位置的置换。
2，然后让头角标自增，尾角标自减，在继续位置转换。
3，依次类推，知道头角标和尾角标相等时大于就结束。
*/
程序如下：
public static void reverseArry(int[] arr)
{
for (int start=0,end=arr.length-1 ;start<end; start++,end--)
{
swap(arr,star,end);
}

}

作者: zhaosenyang 时间: 2012-7-30 23:29
毕老师的那两个我就不说了，我想了一个自己的思路，你可以参考一下
我的排序方法：
原理：让参与外循环元素的头角标元素和最值元素调换位置。
内循环一次，得到最值角标，与参与外循环的头角标元素调换位置。最值出现参与循环的元素的头角标位置上。
注意：m这个变量存储参与外循环的元素中最值的角标。这个值的初始化值随着a改变，a为去跟其余元素最值调换位置的元素角标，b为跟最值比大小的元素角标。m为最值角标。
好处：内循环每次循环，满足条件在栈内存中进行交换（角标交换），堆内存中不变（数组的值）。
内循环结束，才在堆内存中交换（数组元素位置置换）。这样在栈内存中交换，适当的会节省内存。
*/

public static void arr_sort3(int[]x)
{
for (int a=0;a<x.length ;a++ )
{ int m=a;//m这个变量存储参与外循环的元素中最值的角标。这个值初始化值随着a改变
{ for (int b=a+1;b<x.length;b++ )//内循环一次，得出参与循环的最值元素角标
if (x[m]>x[b])
m=b;
}
int tmp=x[m];//将最值元素与参与循环的头角标元素调换位置。
x[m]=x[a];
x[a]=tmp;
System.out.println(x[a]);//调换位置以后，打印头角标元素即最值。
}
}

}

作者: 王峰 时间: 2012-7-31 00:00
冒泡排序是一种典型的交换排序方法，其思想是让无序的相邻的关键字比较交换，使最小的如气泡浮上来，快速排序是有冒泡排序改进而来的，：冒泡排序的算法如：
int [] temp = {1,2,56,23,89,5};
for (int i = 0; i <temp.length-1; i ++){
for(int j = temp.length - 1;j > i; j --){
if( temp[j]<temp[j-1]){
int tt = temp[j];
temp[j]=temp[j-1];
temp[j-1]=tt;
}
}
快速排序算法：
int i=0;
int j=temp.length;
if(i<j){
int tt = temp[i];
while(i!=j){
while(j>i&&temp[j]<tt)
j---;
temp[i]=temp[j];
while(i<j&&temp[i]<tt)
i--;
temp[j]=temp[i];
}
temp[i]=tt;
//然后递归调用这一段代码即可，分前半段和后半段，瞌睡的很，我睡觉了，晚安，有点乱，希望对你有帮助

}
}

作者: 曹晓涵 时间: 2012-7-31 00:06
冒泡排序：
冒泡排序：不断遍历文件，交换倒序的相邻元素，直到文件排好顺序。
冒泡排序的主要优点是容易实现，冒泡排序通常会比其他排序慢。

public class Bubble {
public int[] array = {8,2,4,7,0,1};
private void sort(){
/*
当i=0时进入第一轮外层循环将第一个元素8依次与后面五个元素比较，若比后面元素大则交换位置，经过第一轮循环后，将最小的元素0换在第一个位置。
{8,2,4,7,0,1}==》{2,8,4,7,0,1}==》{0,8,4,7,2,1}
当i=1时进入第二轮循环将第二个元素8依次与后面四个元素比较，若比后面元素大则交换位置，经过第一轮循环后，将次小的元素1换在第二个位置。
{0,8,4,7,2,1}==》{0,4,8,7,2,1}==》{0,2,8,7,4,1}==>{0,1,8,7,4,2}
当i=2时进入第三轮循环将第三个元素8依次与后面三个元素比较，若比后面元素大则交换位置，经过第一轮循环后，将第三小的元素2换在第三个位置。
{0,1,8,7,4,2}==》{0,1,7,8,4,2}==》{0,1,4,8,7,2}==>{0,1,2,8,7,4}
当i=3时进入第四轮循环将第四个元素8依次与后面两个元素比较，若比后面元素大则交换位置，经过第一轮循环后，将第四小的元素4换在第四个位置。
{0,1,2,8,7,4}==》{0,1,2,7,8,4}==》{0,1,2,4,8,7}
当i=4时进入第五轮循环将第五个元素8依次与最后一个元素比较，若比后面元素大则交换位置，经过第一轮循环后，将第五小的元素7换在第五个位置。
{0,1,2,4,8,7}==》{0,1,2,4,7,8}
当i=5时候，不满足i<array.length-1，退出外层循环比较结束。
*/
for(int i = 0 ; i < array.length-1 ; i ++){
/*当i=0时，内层循环数据交换情况
当j=1时,a[i]=a[0]=8,a[j]=a[1]=2,此时a[0]>a[j]需要交换位置，数组的次序变为{2,8,4,7,0,1}，j自增一次变为2
当j=2时,a[i]=a[0]=2,a[j]=a[2]=4,此时a[0]<a[j]保持原顺序，数组的次序仍为{2,8,4,7,0,1}，j自增一次变为3
当j=3时,a[i]=a[0]=2,a[j]=a[3]=7,此时a[0]<a[j]保持原顺序，数组的次序仍为{2,8,4,7,0,1}，j自增一次变为4
当j=4时,a[i]=a[0]=2,a[j]=a[4]=0,此时a[0]>a[j]需要交换位置，数组的次序仍为{0,8,4,7,2,1}，j自增一次变为5
当j=3时,a[i]=a[0]=0,a[j]=a[5]=1,此时a[0]<a[j]保持原顺序，数组的次序仍为{0,8,4,7,2,1}，j自增一次变为6
当j=6=array.length时候不满足内层循环条件跳出内层循环，i自增一次变为1，进入外层循环，内层循环共执行array.lenght-1次
*/
for(int j = i + 1 ; j < array.length ; j ++){
if(array[i] > array[j])
swap(array , i , j);
}
}
display(array);
}
private void display(int [] a){
for(int i : a)
System.out.print(i + "\t");
}
private void swap(int [] a , int bigger , int smaller){
int temp;
temp = a[bigger];
a[bigger] = a[smaller];
a[smaller] = temp;
}
public static void main(String[] args) {
Bubble b = new Bubble();
b.sort();
}
}

复制代码

快速排序：
快速排序是对冒泡排序的一种改进。原理可以参照http://blog.csdn.net/sws9999/article/details/2791812

public class QuickSort {
public int[] array = {8,2,4,7,0,1};
protected void display(int [] a){
for(int i : a)
System.out.print(i + "\t");
}
protected void swap(int [] a , int bigger , int smaller){
int temp;
temp = a[bigger];
a[bigger] = a[smaller];
a[smaller] = temp;
}
/**
*
* 对三点进行排序
*
* @param a
* @param first
* @param mid
* @param last
*/
private void sortPivots(int [] a , int first , int mid , int last){
sortForTwo(a, first, mid);
sortForTwo(a , mid , last);
sortForTwo(a, first, mid);
}
private void sortForTwo(int [] a , int before , int after){
if(a[before] > a[after]){
swap(a, before, after);
}
}
private int partition(int [] a, int first , int last){
//设置支点
int mid = (first + last)/2;
sortPivots(a, first, mid, last);
//将支点移动到数组中的倒数第二个位置
swap(a, mid, last - 1);
int pivotIndex = last - 1;
int pivot = a[pivotIndex];
//确定子数组
int indexFromLeft = first + 1;
int indexFromRight = last - 2;
boolean done = false;
while(!done){
//从数组的左边开始，留下小于支点的元素
while(a[indexFromLeft] < pivot)
indexFromLeft++;
//从数组的右边开始，留下大于支点的元素
while(a[indexFromRight] > pivot)
indexFromRight--;
//交换数据
if(indexFromLeft < indexFromRight){
swap(a, indexFromLeft, indexFromRight);
indexFromLeft ++;
indexFromRight--;
}else
done = true;
}
//将支点放在较小部分和较大部分字数组之间
swap(a, pivotIndex, indexFromLeft);
pivotIndex = indexFromLeft;
return pivotIndex;
}
private int [] sort(int [] a , int first , int last){
if(last - first + 1 < 4){
//选择别的排序
for(int i = 0 ; i < a.length ; i ++){
for(int j = i + 1 ; j < a.length ; j ++){
if(a[i] > a[j])
swap(a , i , j);
}
}
}else{
//创建划分
int pivotIndex = partition(array, first, last);
//对较小部分和较大部分分别进行快速排序
sort(a, first, pivotIndex - 1);
sort(a, pivotIndex + 1 , last);
}
return array;
}
public static void main(String[] args) {
QuickSort q = new QuickSort();
q.array = q.sort(q.array, 0 , q.array.length - 1);
q.display(q.array);
}
}

复制代码

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2