黑马程序员技术交流社区

标题: Java中的选择排序的算法 求一个大神给个快速排序的写法 [打印本页]
作者: zfr930102    时间: 2016-6-24 12:03
标题: Java中的选择排序的算法 求一个大神给个快速排序的写法
  1. public class Demo6_Sort {
  2.         public static void main(String[] args) {
  3.                 int[] arr = {36,21,10,56,78,99};
  4.                 QuestSort qs = new QuestSort();
  5.                 int[] arrays = qs.questSort(arr);
  6.                 for(int i = 0;i<arrays.length;i++) {
  7.                         System.out.print(arrays[i]+" ");
  8.                 }
  9.         }
  10. }
  11. class QuestSort {
  12.         /*
  13.                 快速排序
  14.                 标记位 初始比较数 循环次数
  15.         */
  16.         public int[] questSort(int[] arr) {
  17.                 int temp = 0;
  18.                 int key = 0;
  19.                 for(int i = 0;i<arr.length;i++) {
  20.                         temp = arr[0];
  21.                         key = 0;
  22.                         for(int j = 0;j<arr.length-i;j++) {
  23.                                 if(temp>arr[j]) {
  24.                                         temp = arr[j];
  25.                                         key = j;
  26.                                 }
  27.                         }
  28.                         arr[key] = arr[arr.length-i-1];
  29.                         arr[arr.length-i-1] = temp;
  30.                 }
  31.                 return arr;
  32.         }
  33. }
  34. class
  35. {
  36. }
复制代码
作者: 我有上将潘凤    时间: 2016-6-24 16:38
  1. package cn.hyh_01;
  2. import java.util.Arrays;
  3. /*
  4. * 首先得明白快速排序的思想：
  5. *         第一阶段：
  6. *                 1.将数组的第一个元素5（索引为0）与数组最后一个元素（索引为8）开始向左比较，找到比他小的就交换位置，
  7. *                       如：（5，9，2，1，6，4，10，7，8）比较结束后变成（4，9，2，1，6，5，10，7，8），即5和4换了一个位置.
  8. *                 2.再将5（索引为5）和第二个元素（索引为1）开始向右比较，找到比它大的就换位置，得（4，5，2，1，6，9，10，7，8），即5和9换位.
  9. *                 3.再将5（索引为1）和第五个元素（索引为4）开始向左比较，找到比它小的就换位置，得（4，1，2，5，6，9，10，7，8），即5和1换位.
  10. *                 4.再将5（索引为3）和第三个元素（索引为2）开始向右比较，找到比它大的就换位置，结果没找到，至此5的位置寻找结束，
  11. *                         得到的结果是，5左边的数字都比它小，5右边的数字都比它大。
  12. *         第二阶段：
  13. *                 1.从第一阶段我们得到了5在数组中的位置，并且5将数组分割成了两部分，分别是（4，1，2）和（6，9，10，7，8），这时，
  14. *                         我们分别将第一部分和第二部分看成是一个独立的整体，重复第一阶段得到结果是：
  15. *                       （1，2，4）和（6，9，10，7，8）这时4和6的位置也确定了
  16. *                 2.我们又得到两部分（1，2）和（9，10，7，8），继续重复第一阶段得到结果是：
  17. *                     （1）和（8，10，7，9）——（8，9，7，10）——（8，7，9，10），这时1和9的位置也确定了
  18. *                 3.我们又得到两部分（8，7）和（10），通过第一阶段的比较得到（7，8）和（10）这时8和10的位置确定
  19. *                 4.最后只剩（7），通过第一阶段的比较也确定了它的位置，至此排序结束。
  20. *         下面来进行代码实现：
  21. */
  22. public class QuickSort {
  23.         public static void main(String[] args) {
  24.                 int[] arr = {5,9,2,1,6,4,10,7,81,1,8,6,5,3};
  25.                 quickSort(arr,0,arr.length-1);
  26.                 System.out.println(Arrays.toString(arr));

  28.         }

  30.         // 首先实现第一阶段的代码,通过定义一个方法：
  31.         /*
  32.          * 明确参数列表：
  33.          *                 1.被排序的数组
  34.          *                 2.要寻找最终位置的数据在数组中的初始位置
  35.          *                 3.从哪里开始比较（要比较的最大索引处，即最大边界）
  36.          * 明确返回值：
  37.          *                 被寻找值的最终索引
  38.          */
  39.         public static int search(int[] arr, int target, int maxIndex) {
  40.                 int start = 0;        //初始化最小边界
  41.                 while (start < maxIndex) {        //最小边界大于或等于最大边界的时候就可以认为循环结束了。
  42.                         // 1.从右向左比较
  43.                         start = target + 1;        //确定最小边界
  44.                         for (int i = maxIndex; i >= start; i--) {
  45.                                 if (arr[target] > arr[i]) {
  46.                                         // 找到比自己小的就换位置
  47.                                         arr[target] = arr[i] ^ arr[target] ^ (arr[i] = arr[target]);
  48.                                         // 并且继续用target记录自己的位置
  49.                                         target = i;
  50.                                         //找到了就跳出循环
  51.                                         break;
  52.                                 }
  53.                         }
  54.                         // 2.从左向右比较
  55.                         maxIndex = target - 1;        //确定最大边界
  56.                         for (int i = start; i <= maxIndex; i++) {
  57.                                 if (arr[target] < arr[i]) {
  58.                                         // 找到比自己大的就换位置
  59.                                         arr[target] = arr[i] ^ arr[target] ^ (arr[i] = arr[target]);
  60.                                         // 并且继续用target记录自己的位置
  61.                                         target = i;
  62.                                         //找到了就跳出循环
  63.                                         break;
  64.                                 }
  65.                         }
  66.                 }
  67.                 return target;
  68.         }
  69.        
  70.         //第二阶段代码：
  71.                 /* 经过简单的思考我们可以知道，第二阶段的循环嵌套次数是未知的（注意：不仅仅是循环次数未知），
  72.                  * 对于这种循环中嵌套循环，且嵌套次数未知的情况，我们使用方法的递归来实现：
  73.                  * 参数列表：
  74.                  *                 在这个递归函数中我们将会用到之前定义的函数，所以参数列表与search方法的一致.
  75.                  * 返回值类型：
  76.                  *                 只需要该方法为我们完成排序的需求，所以无返回值。
  77.                  *
  78.                  */
  79.         public static void quickSort(int[] arr,int start,int end) {
  80.                 //得到arr[start]的位置,并且将数组分成了俩部分
  81.                 int target = search(arr,start,end);
  82.                 if (start<target-1) {
  83.                         //这里用来排序左边部分
  84.                         quickSort(arr,start,target-1);
  85.                 }
  86.                 if (target+1<end) {
  87.                         //这里用来排序右边部分
  88.                         quickSort(arr,target+1,end);
  89.                 }
  90.                 return;
  91.         }
  92. }
复制代码


作者: 940752944    时间: 2016-6-24 19:19
package cn.itcast;

/*
* 快速排序：
* 一趟快速排序的算法是： 　　
* 1）设置两个变量i、j，排序开始的时候：i=0，j=N-1； 　　
* 2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]； 　　
* 3）从j开始向前搜索，即由后开始向前搜索（j=j-1即j--），
* 找到第一个小于key的值A[j]，A[i]与A[j]交换； 　　
* 4）从i开始向后搜索，即由前开始向后搜索（i=i+1即i++），
* 找到第一个大于key的A[i]，A[i]与A[j]交换； 　　
* 5）重复第3、4、5步，直到 I=J；
* (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。
* 找到并交换的时候i， j指针位置不变。
* 另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。）
*/
public class QuickSort {
        public static void sort(int[] data) {
                quickSort(data, 0, data.length - 1);
        }

        private static void quickSort(int[] data, int i, int j) {
                int pivotIndex = (i + j) / 2;
                // swap
                SortTest.swap(data, pivotIndex, j);

                int k = partition(data, i - 1, j, data[j]);
                SortTest.swap(data, k, j);
                if ((k - i) > 1)
                        quickSort(data, i, k - 1);
                if ((j - k) > 1)
                        quickSort(data, k + 1, j);

        }

        /**
         * @param data
         * @param i
         * @param j
         * @return
         */
        private static int partition(int[] data, int l, int r, int pivot) {
                do {
                        while (data[++l] < pivot)
                                ;
                        while ((r != 0) && data[--r] > pivot)
                                ;
                        SortTest.swap(data, l, r);
                } while (l < r);
                SortTest.swap(data, l, r);
                return l;
        }
}
作者: zfr930102    时间: 2016-6-27 12:37
我有上将潘凤 发表于 2016-6-24 16:38

谢谢 大神指点
作者: gaojiangjian    时间: 2016-6-27 22:06
冒泡排序
int arr[];
int lenth=arr.size();
for(int i=0;i<lenth-1;i++){
for(int j=0;j<len-i-1;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
选择排序
for(int i=0;i<len-1;i++){
for(int j=0;j<len;j++){
if(arr[x]>arr[y]){
int temp=arr[x];
arr[x]=arr[y];
arr[y]=temp;
}
}
}



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