黑马程序员技术交流社区

标题: 谁有快速排序的正确代码？ [打印本页]

---

作者: JJJD    时间: 2015-6-25 19:08
标题: 谁有快速排序的正确代码？
请问谁有快速排序的正确代码？谢谢了！

---

作者: keto    时间: 2015-6-25 20:04
/*
* 冒泡排序：将每个元素取出，跟相邻的元素进行比较，如果从小到大排序，判断当前元素如果大于相邻元素，则进行交换。      
*/
public class Demo {
        public static void main(String[] args) {
                int[] arr = {3,24,32,36,7,8};
               
                //冒泡排序
                for(int i = 0; i < arr.length - 1 ; i++){//外层循环控制循环次数
                        for(int j = 0 ; j < arr.length - 1 - i ; j++){//内层循环用于取数字，并比较
                                if(arr[ j ] > arr[ j + 1] ){
                                        //交换
                                        int temp = arr[ j ];
                                        arr[ j ] = arr[ j + 1];
                                        arr[ j + 1] = temp;
                                }
                        }
                }
                printArray(arr);
        }
       
        public static void printArray(int[] arr){
                for(int i = 0;i < arr.length ; i++){
                        System.out.println(arr[i]);
                }
        }
}

/*
* 选择排序：
*
* 从0索引开始，依次和后面元素比较，小的往前放，第一次完毕，最小值出现在了最小索引处
*/
public class Demo {
        public static void main(String[] args) {
                int[] arr = {88,45,75,20,10};
                //方式一：比较一次，就交换一次。由于有很多的无效交换，所以效率低。
                /*for(int i = 0;i < arr.length - 1 ; i++){
                        for(int j = i + 1 ; j < arr.length ; j++){
                                //判断如果i > j的数，就交换
                                if(arr[i] > arr[j]){
                                        //交换
                                        int temp = arr[i];
                                        arr[i] = arr[j];
                                        arr[j] = temp;
                                }
                        }
                }
                printArray(arr);*/
               
                //方式二：先进行判断，并寻找最小数，找到后，不交换，只记录索引值。每个数都遍历了之后，每一轮的最后只进行一次交换。
               
                //实际上，上边的实现方式，有很多无效的交换：这种交换，不是最终的结果。
                //大家考虑：实际上每一轮都是找最小数的过程，找到后，跟第一个数一交换，只要保证第一个数是最小的就可以。
                for(int i = 0;i < arr.length - 1 ;i ++){
                        //思路：找最小的数，然后把最小数的索引记录下来，最后再进行交换
                        int minIndex = i;//假设第一个数就是最小的，将索引记录下来
                        for(int j = i + 1; j < arr.length ; j++){
                                if(arr[minIndex] > arr[j]){
                                        //不交换，把索引记录下来
                                        minIndex = j;
                                }
                        }
                        //内部的j循环一结束，minIndex记录的就是最小数的索引
                        if(minIndex != i){//有其它更小的数，执行交换
                                int temp = arr[i];
                                arr[i] = arr[minIndex];
                                arr[minIndex] = temp;
                        }
                }
               
                printArray(arr);
               
        }
        public static void printArray(int[] arr){
                for(int i = 0;i < arr.length ; i++){
                        System.out.println(arr[i]);
                }
        }
}

---

作者: jx5785749    时间: 2015-6-25 21:40


package src;

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);
            System.out.print(" ");
        }
    }
}

---

作者: 我是隔壁老王呀    时间: 2015-6-25 22:06
给你一份链接，是关于我关于快速排序的理解，以及详细代码分析。
快速排序算法

---

作者: JJJD    时间: 2015-6-26 11:50
谢谢大家了，学习啦。。。

---

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

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