黑马程序员技术交流社区

标题: 求数组的冒泡排序，交换排序和快速排序的原理与实现 [打印本页]
作者: 梁胜海    时间: 2012-11-4 20:40
标题: 求数组的冒泡排序，交换排序和快速排序的原理与实现
本帖最后由 梁胜海 于 2012-11-4 22:21 编辑

求大神帮忙解释下数组中的这三种数组排序冒泡排序，交换排序和快速排序。一直数组都是我的软肋，有木有，举手啊。
作者: 葬天    时间: 2012-11-4 20:44
/**
排序练习
@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);
                }
        }
       
        /**
        快排的划分
        做法
　　第一步：(初始化)设置两个指针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]+"]");
                        }
                }
        }
}

当时 学习时的小练习，你可以看一下
作者: 陈云展    时间: 2012-11-4 21:33
  1. package com.itheima;

  3. import java.util.Arrays;

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

  20.         // 冒泡排序法
  21.         public static int[] sort1(int[] arr) {
  22.                 for (int i = 0; i < arr.length; i++) {
  23.                         int temp = 0;
  24.                         for (int j = 0; j < arr.length - i - 1; j++) {
  25.                                 if (arr[j] > arr[j + 1]) {
  26.                                         temp = arr[j];
  27.                                         arr[j] = arr[j + 1];
  28.                                         arr[j + 1] = temp;
  29.                                 }
  30.                         }
  31.                 }
  32.                 return arr;
  33.         }

  35.         // 插入排序法
  36.         public static int[] sort2(int[] arr, int left, int right) {
  37.                 for (int i = left, j = i; i < right; j = ++i) {
  38.                         int arri = arr[i + 1];
  39.                         while (arri < arr[j]) {
  40.                                 arr[j + 1] = arr[j];
  41.                                 if (j-- == left) {
  42.                                         break;
  43.                                 }
  44.                         }
  45.                         arr[j + 1] = arri;
  46.                 }
  47.                 return arr;
  48.         }

  50.         // 选择排序法
  51.         public static int[] sort3(int[] arr) {
  52.                 for (int i = 0; i < arr.length - 1; i++) {
  53.                         int j = i;
  54.                         int temp = 0;
  55.                         for (int k = i + 1; k < arr.length; k++) {
  56.                                 if (arr[k] < arr[j]) {
  57.                                         j = k;
  58.                                 }
  59.                         }
  60.                         if (j != i) {
  61.                                 temp = arr[j];
  62.                                 arr[j] = arr[i];
  63.                                 arr[i] = temp;
  64.                         }
  65.                 }
  66.                 return arr;
  67.         }

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

  83.                 middle = arr[(left + right) / 2];
  84.                 do {
  85.                         while ((arr[i] < middle) && (i < right)) {
  86.                                 i++;
  87.                         }
  88.                         while ((arr[j] > middle) && (j > left)) {
  89.                                 j--;
  90.                         }
  91.                         if (i <= j) {
  92.                                 temp = arr[i];
  93.                                 arr[i] = arr[j];
  94.                                 arr[j] = temp;
  95.                                 i++;
  96.                                 j--;
  97.                         }
  98.                 } while (i <= j);
  99.                 if (left < j) {
  100.                         sort4(arr, left, j);
  101.                 }

  103.                 if (right > i)
  104.                         sort4(arr, i, right);
  105.                 return arr;
  106.         }

  108.         public static int[] sort5(int[] arr, int step) {
  109.                 int min;
  110.                 int temp;

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

  117.                 while (sequence > 0) {

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

  123.                                 while (min > sequence - 1 && arr[min - sequence] > temp) {
  124.                                         arr[min] = arr[min - sequence];
  125.                                         min = min - sequence;
  126.                                 }

  128.                                 arr[min] = temp;
  129.                         }

  131.                         sequence = (sequence - 1) / step; // 递减序列关键字
  132.                 }
  133.                 return arr;
  134.         }

  136.        
  137.         /**
  138.          * 归并操作的工作原理如下：
  139.          * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  140.          * 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  141.          * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  142.          * 　重复步骤3直到某一指针达到序列尾
  143.          * 将另一序列剩下的所有元素直接复制到合并序列尾
  144.          * @param data1
  145.          * @param data2
  146.          * @return
  147.          */
  148.         public static int[] sort6(int[] data1, int[] data2) {
  149.                 int[] temp = new int[data1.length + data2.length];
  150.                 int i = 0, j = 0, iter = 0;
  151.                 for (; i < data1.length && j < data2.length;) {
  152.                         if (data1[i] <= data2[j]) {
  153.                                 temp[iter] = data1[i];
  154.                                 iter++;
  155.                                 i++;
  156.                         } else {
  157.                                 temp[iter] = data2[j];
  158.                                 iter++;
  159.                                 j++;
  160.                         }
  161.                 }
  162.                 for (; i < data1.length; i++, iter++) {
  163.                         temp[iter] = data1[i];
  164.                 }
  165.                 for (; j < data2.length; j++, iter++) {
  166.                         temp[iter] = data2[j];
  167.                 }
  168.                 return temp;
  169.         }

  171. }
复制代码
作者: 梁胜海    时间: 2012-11-4 22:21
葬天 发表于 2012-11-4 20:44
/**
排序练习
@author yangmeicheng

嗯，好的
作者: 梁胜海    时间: 2012-11-4 22:21
陈云展 发表于 2012-11-4 21:33
  • 自己总结的
  • 这里给你推荐一个好网站
  • 建议：静下心。debug。思考。总结。

    • 不错，我试试



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