A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 梁胜海 于 2012-11-4 22:21 编辑

求大神帮忙解释下数组中的这三种数组排序冒泡排序,交换排序和快速排序。一直数组都是我的软肋,有木有,举手啊。

4 个回复

倒序浏览
/**
排序练习
@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]+"]");
                        }
                }
        }
}

当时 学习时的小练习,你可以看一下
回复 使用道具 举报
  1. package com.itheima;

  2. import java.util.Arrays;

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

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

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

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

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

  76.                 middle = arr[(left + right) / 2];
  77.                 do {
  78.                         while ((arr[i] < middle) && (i < right)) {
  79.                                 i++;
  80.                         }
  81.                         while ((arr[j] > middle) && (j > left)) {
  82.                                 j--;
  83.                         }
  84.                         if (i <= j) {
  85.                                 temp = arr[i];
  86.                                 arr[i] = arr[j];
  87.                                 arr[j] = temp;
  88.                                 i++;
  89.                                 j--;
  90.                         }
  91.                 } while (i <= j);
  92.                 if (left < j) {
  93.                         sort4(arr, left, j);
  94.                 }

  95.                 if (right > i)
  96.                         sort4(arr, i, right);
  97.                 return arr;
  98.         }

  99.         public static int[] sort5(int[] arr, int step) {
  100.                 int min;
  101.                 int temp;

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

  106.                 while (sequence > 0) {

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

  110.                                 while (min > sequence - 1 && arr[min - sequence] > temp) {
  111.                                         arr[min] = arr[min - sequence];
  112.                                         min = min - sequence;
  113.                                 }

  114.                                 arr[min] = temp;
  115.                         }

  116.                         sequence = (sequence - 1) / step; // 递减序列关键字
  117.                 }
  118.                 return arr;
  119.         }

  120.        
  121.         /**
  122.          * 归并操作的工作原理如下:
  123.          * 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  124.          * 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  125.          * 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  126.          *  重复步骤3直到某一指针达到序列尾
  127.          * 将另一序列剩下的所有元素直接复制到合并序列尾
  128.          * @param data1
  129.          * @param data2
  130.          * @return
  131.          */
  132.         public static int[] sort6(int[] data1, int[] data2) {
  133.                 int[] temp = new int[data1.length + data2.length];
  134.                 int i = 0, j = 0, iter = 0;
  135.                 for (; i < data1.length && j < data2.length;) {
  136.                         if (data1[i] <= data2[j]) {
  137.                                 temp[iter] = data1[i];
  138.                                 iter++;
  139.                                 i++;
  140.                         } else {
  141.                                 temp[iter] = data2[j];
  142.                                 iter++;
  143.                                 j++;
  144.                         }
  145.                 }
  146.                 for (; i < data1.length; i++, iter++) {
  147.                         temp[iter] = data1[i];
  148.                 }
  149.                 for (; j < data2.length; j++, iter++) {
  150.                         temp[iter] = data2[j];
  151.                 }
  152.                 return temp;
  153.         }

  154. }
复制代码
  • 自己总结的
  • 这里给你推荐一个好网站
  • 建议:静下心。debug。思考。总结。
  • http://en.wikipedia.org/wiki/Sorting_algorithm
回复 使用道具 举报
葬天 发表于 2012-11-4 20:44
/**
排序练习
@author yangmeicheng

嗯,好的
回复 使用道具 举报
陈云展 发表于 2012-11-4 21:33
  • 自己总结的
  • 这里给你推荐一个好网站
  • 建议:静下心。debug。思考。总结。

  • 不错,我试试
    回复 使用道具 举报
    您需要登录后才可以回帖 登录 | 加入黑马