黑马程序员技术交流社区

标题: 一个快排的问题 [打印本页]

作者: 刘文飞 时间: 2012-11-13 21:27
标题: 一个快排的问题
本帖最后由刘文飞于 2012-11-14 10:05 编辑

编译没有出错，但是运行没有输出。
====================================

复制代码

作者: 聽聽我dē❤ 时间: 2012-11-13 21:46
貌似好麻烦啊

作者: 李桐 时间: 2012-11-13 22:00
貌似方法没有返回值啊

作者: 蔡兆军 时间: 2012-11-13 22:05
第二十四行在while循环里面怎么会return low；我编译了以下这里不行

作者: 蔡兆军 时间: 2012-11-13 22:09
额我复制过来少了个{ 。编译没结果不知道怎么回事

作者: 刘文飞 时间: 2012-11-13 22:11

李桐发表于 2012-11-13 22:00
貌似方法没有返回值啊

貌似在哪啊

作者: 刘文飞 时间: 2012-11-13 22:12

蔡兆军发表于 2012-11-13 22:05
第二十四行在while循环里面怎么会return low；我编译了以下这里不行

return low是在while循环外的呢

作者: 陈莹 时间: 2012-11-13 22:16
因为你的程序陷入死循环了，所以那个输出语句就没有执行，当然就没有输出结果了

作者: 李桐 时间: 2012-11-13 22:18

刘文飞发表于 2012-11-13 22:11
貌似在哪啊

quickSort方法的返回值是void吧

作者: 刘文飞 时间: 2012-11-13 22:26

李桐发表于 2012-11-13 22:18
quickSort方法的返回值是void吧

对，是写着void额:L

作者: 刘文飞 时间: 2012-11-13 22:26

陈莹发表于 2012-11-13 22:16
因为你的程序陷入死循环了，所以那个输出语句就没有执行，当然就没有输出结果了 ...

怎么个死法呢

作者: 刘文飞 时间: 2012-11-13 22:27

陈莹发表于 2012-11-13 22:16
因为你的程序陷入死循环了，所以那个输出语句就没有执行，当然就没有输出结果了 ...

怎么个死法呢

作者: 张综 时间: 2012-11-13 22:39
几种快排的方法，你好好研究研究吧。一起努力。。
/**
排序练习
@author yangmeicheng
*/
class SortTest
{
      public static void main(String[] args)
      {
            int [] arr = new int[] {1,78,34,13,14,20};
            System.out.println("排序前：");
            printArray(arr);
            //sortSelect(arr);
            //bubbleSort(arr);
            //insertSort(arr);
            quickSort(arr,0,arr.length-1);
            System.out.println("排序后");
            printArray(arr);
      }

      /**
      选择排序算法
      原理：工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
               然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
            以此类推，直到所有元素均排序完毕。
      复杂度分析：选择排序的交换操作介于和次之间。选择排序的比较操作为次之间。选择排序的赋值操作介于和次之间。
                  比较次数O(n^2),比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。
                              交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。
                              交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
      @param arr待排序数组
      */
      public static void sortSelect( int [] arr )
      {
            for (int i=0; i<arr.length-1; i++ )
            {
                     for(int j=i+1; j<arr.length; j++)
                     {
                              if(arr[j] < arr[i])
                              {
                                    arr[j] = arr[i]^arr[j];
                                    arr[i] = arr[i]^arr[j];
                                    arr[j] = arr[i]^arr[j];
                              }
                     }
            }
      }

      /**
      完成冒泡排序
      原理：
            比较相邻的元素。如果第一个比第二个大，就交换他们两个。
            对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
            针对所有的元素重复以上的步骤，除了最后一个。
            持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
            由于它的简洁，冒泡排序通常被用来对于程式设计入门的学生介绍算法的概念。
      复杂度分析：冒泡排序对个项目需要O()的比较次数，且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一，
                              但它对于少数元素之外的数列排序是很没有效率的。
                              冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要次交换，
                              而插入排序只要最多交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（），而插入排序在这个例子只需要个运算。
      @param arr待排序数组
      */
      public static void bubbleSort(int [] arr)
      {
            for (int i=0; i<arr.length-1;i++)
            {
                     for (int j=0;j<arr.length-i-1;j++)
                     {
                              if(arr[j+1] > arr[j])
                              {
                                    arr[j+1] = arr[j+1]^arr[j];
                                    arr[j] = arr[j+1]^arr[j];
                                    arr[j+1] = arr[j+1]^arr[j];
                              }
                     }
            }
      }

      /**
      完成插入排序
      原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
      步骤：
            从第一个元素开始，该元素可以认为已经被排序
            取出下一个元素，在已经排序的元素序列中从后向前扫描
            如果该元素（已排序）大于新元素，将该元素移到下一位置
            重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
            将新元素插入到该位置后
            重复步骤2~5
      复杂度分析：
                              插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，
                              需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
      */
      public static void insertSort(int arr[])
      {
            for (int i=1;i<arr.length;i++ )
            {
                     int key = arr[i];
                     int position = i;

                     while (position > 0 && arr[position-1]>key)
                     {
                              arr[position] = arr[position-1];
                              position --;
                     }
                     arr[position] = key;
            }
      }

      /**
      完成快速排序
      原理：快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
      步骤为：
            从数列中挑出一个元素，称为 "基准"（pivot），
            重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
            在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
            递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
            递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，
            但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
      复杂分析：在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，
                        但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，
                        因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
      */
      public static void quickSort(int [] arr,int low, int high)
      {
            int pivot;
            if (low < high)
            {
                     pivot = getCurrent(arr,low,high);
                     quickSort(arr,low,pivot-1);
                     quickSort(arr,pivot+1,high);
            }
      }

作者: 张综 时间: 2012-11-13 22:40
  /**
      快排的划分
      做法
　　第一步：(初始化)设置两个指针i和j，它们的初值分别为区间的下界和上界，即i=low，i=high；
                     选取无序区的第一个记录R[i](即R[low])作为基准记录，并将它保存在变量pivot中；
　　第二步：令j自high起向左扫描，直到找到第1个关键字小于pivot.key的记录R[j]，
                     将R[j])移至i所指的位置上，这相当于R[j]和基准R[i](即pivot)进行了交换，
                     使关键字小于基准关键字pivot.key的记录移到了基准的左边，交换后R[j]中相当于是pivot；
                     然后，令i指针自i+1位置开始向右扫描，直至找到第1个关键字大于pivot.key的记录R[i]，
                     将R[i]移到i所指的位置上，这相当于交换了R[i]和基准R[j]，使关键字大于基准关键字的记录移到了基准的右边，
                     交换后R[i]中又相当于存放了pivot；接着令指针j自位置j-1开始向左扫描，如此交替改变扫描方向，
                     从两端各自往中间靠拢，直至i=j时，i便是基准pivot最终的位置，将pivot放在此位置上就完成了一次划分。
      */
      public static int getCurrent(int [] arr, int low, int high)
      {
            int pivot = arr[low];
            while (low < high )
            {
                     while (low<high && arr[high] >= pivot)
                     {
                              high--;
                     }
                     if (low < high)
                     {
                              arr[low++] = arr[high];
                     }
                     while (low < high && arr[low] <= pivot)
                     {
                              low ++;
                     }
                     if (low < high)
                     {
                              arr[high--] = arr[low];
                     }
            }
            //arr[low] = pivot;
            arr[high] = pivot;
            return low;
      }

      /**

      完成数组的打印功能
      */
      public static void printArray(int [] arr)
      {
            System.out.print("[");
            for(int i=0; i<arr.length; i++)
            {
                     if( i != arr.length-1 )
                     {
                              System.out.print(arr[i]+", ");
                     }
                     else
                     {
                              System.out.println(arr[i]+"]");
                     }
            }
      }
}

package com.itheima;

import java.util.Arrays;

/**
* 1、排序有哪几种方法？请列举。并用JAVA实现一个快速排序.
*
* @author snow
*
*/
public class Test1 {
      public static void main(String[] args) {
            int arr[] = new int[] { 10, 8, 20, 11, 19 };
            // int[] a = {2, 34, 2};// 一个数组的定义和实例化
            // System.out.println(Arrays.toString(sort2(arr)));
            System.out.println(Arrays.toString(sort4(arr, 0, arr.length - 1)));
            System.out.println(Arrays.toString(sort6(arr, arr)));
      }

      // 冒泡排序法
      public static int[] sort1(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                     int temp = 0;
                     for (int j = 0; j < arr.length - i - 1; j++) {
                              if (arr[j] > arr[j + 1]) {
                                    temp = arr[j];
                                    arr[j] = arr[j + 1];
                                    arr[j + 1] = temp;
                              }
                     }
            }
            return arr;
      }

      // 插入排序法
      public static int[] sort2(int[] arr, int left, int right) {
            for (int i = left, j = i; i < right; j = ++i) {
                     int arri = arr[i + 1];
                     while (arri < arr[j]) {
                              arr[j + 1] = arr[j];
                              if (j-- == left) {
                                    break;
                              }
                     }
                     arr[j + 1] = arri;
            }
            return arr;
      }

      // 选择排序法
      public static int[] sort3(int[] arr) {
            for (int i = 0; i < arr.length - 1; i++) {
                     int j = i;
                     int temp = 0;
                     for (int k = i + 1; k < arr.length; k++) {
                              if (arr[k] < arr[j]) {
                                    j = k;
                              }
                     }
                     if (j != i) {
                              temp = arr[j];
                              arr[j] = arr[i];
                              arr[i] = temp;
                     }
            }
            return arr;
      }

      // 快速排序法
      /**
      * 快速排序思想： 1，首先找到中间的数，i初始为0递增，直到大于或等于中间的数。j初始为length-1递减，直到小于或者等于中间的数。
      * 2，交换i，j所指向的数。
      * 3，递归调用该方法。
      * @param arr
      * @param left
      * @param right
      * @return
      */
      public static int[] sort4(int[] arr, int left, int right) {
            int i = left, j = right;
            int middle, temp;

            middle = arr[(left + right) / 2];
            do {
                     while ((arr[i] < middle) && (i < right)) {
                              i++;
                     }
                     while ((arr[j] > middle) && (j > left)) {
                              j--;
                     }
                     if (i <= j) {
                              temp = arr[i];
                              arr[i] = arr[j];
                              arr[j] = temp;
                              i++;
                              j--;
                     }
            } while (i <= j);
            if (left < j) {
                     sort4(arr, left, j);
            }

            if (right > i)
                     sort4(arr, i, right);
            return arr;
      }

      public static int[] sort5(int[] arr, int step) {
            int min;
            int temp;

            int sequence = 1;
            while (sequence < arr.length / step) {
                     sequence = sequence * step + 1; // 产生到以step为步长到arr.length的最大值.
            }

            while (sequence > 0) {

                     for (int i = sequence; i < arr.length; i++) {
                              temp = arr[i];
                              min = i;

                              while (min > sequence - 1 && arr[min - sequence] > temp) {
                                    arr[min] = arr[min - sequence];
                                    min = min - sequence;
                              }

                              arr[min] = temp;
                     }

                     sequence = (sequence - 1) / step; // 递减序列关键字
            }
            return arr;
      }


      /**
      * 归并操作的工作原理如下：
      * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
      * 设定两个指针，最初位置分别为两个已经排序序列的起始位置
      * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
      * 　重复步骤3直到某一指针达到序列尾
      * 将另一序列剩下的所有元素直接复制到合并序列尾
      * @param data1
      * @param data2
      * @return
      */
      public static int[] sort6(int[] data1, int[] data2) {
            int[] temp = new int[data1.length + data2.length];
            int i = 0, j = 0, iter = 0;
            for (; i < data1.length && j < data2.length;) {
                     if (data1[i] <= data2[j]) {
                              temp[iter] = data1[i];
                              iter++;
                              i++;
                     } else {
                              temp[iter] = data2[j];
                              iter++;
                              j++;
                     }
            }
            for (; i < data1.length; i++, iter++) {
                     temp[iter] = data1[i];
            }
            for (; j < data2.length; j++, iter++) {
                     temp[iter] = data2[j];
            }
            return temp;
      }

}

作者: 刘文飞 时间: 2012-11-13 23:22

张综发表于 2012-11-13 22:40
/**
快排的划分
做法

看完了，还是没发现那段代码错在哪里，怎么没有输出了

作者: 刘腾 时间: 2012-11-14 00:26

//修改后的代码
public class QuickSortDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {12,2,66,9,27,15,91,83,3,10};
quickSort(a,0,a.length-1);
for(int i=0;i<a.length;i++){
System.out.print(a[i] + " ");
}
}
public static int getMiddle(int[] arr, int low, int high){
int temp = arr[low];
while (low < high) {
while (low < high && temp <= arr[high]){
high--;
}
if(low<high) //我感觉这个地方得判断一下
{
arr[low] = arr[high];
}
//小于中轴值的放到前面
while(low < high && temp >= arr[low]){
low++;
}
if(low<high) //还有这个地方也应该判断一下
arr[high] = arr[low]; //大于中轴值的放到后面
}
arr[low] = temp;
return low;
}
/*
public static void quickSort(int[] arr,int low,int high){
while(low < high){//问题出现在这里，这里不应该用循环语句，在这里出现了死循环
int middle = getMiddle(arr, low, high);
quickSort(arr, low, middle-1); //小于中轴值的前半部分
quickSort(arr, middle+1, high); //大于中轴值的后半部分
}
}
*/
/*
下面是正确的函数
*/
public static void quickSort(int[] arr,int low,int high){
if(low < high)
{
int middle = getMiddle(arr, low, high);
quickSort(arr, low, middle-1); //小于中轴值的前半部分
quickSort(arr, middle+1, high); //大于中轴值的后半部分
}
}
}

复制代码

作者: 汤瑞贺 时间: 2012-11-14 00:37
你的只要把27行的,while改成if即可输出

作者: 刘文飞 时间: 2012-11-14 10:04

汤瑞贺发表于 2012-11-14 00:37
你的只要把27行的,while改成if即可输出

正解啊啊啊啊:hug:

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

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