美文网首页
数组排序

数组排序

作者: like65 | 来源:发表于2017-08-02 14:10 被阅读0次

    /**
    * 冒泡法排序
    *比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    *对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
    *针对所有的元素重复以上的步骤,除了最后一个。
    *持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
    *@paramnumbers 需要排序的整型数组*/

    public static voidbubbleSort(int[] numbers) {
    inttemp;// 记录临时中间值
    intsize = numbers.length;// 数组大小
    for(inti =0; i < size -1; i++) {
    for(intj = i +1; j < size; j++) {
    if(numbers[i] < numbers[j]) {// 交换两数的位置

    temp = numbers[i];

    numbers[i] = numbers[j];

    numbers[j] = temp;

    }

    }

    }

    }

    /**

    * 快速排序

    *

      *

      从数列中挑出一个元素,称为“基准”

      *

      重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,

      * 该基准是它的最后位置。这个称为分割(partition)操作。

      *

      递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

      *

      *

      *@paramnumbers

      *@paramstart

      *@paramend

      */

      public static voidquickSort(int[] numbers,intstart,intend) {

      if(start < end) {

      intbase = numbers[start];// 选定的基准值(第一个数值作为基准值)

      inttemp;// 记录临时中间值

      inti = start, j = end;

      do{

      while((numbers[i] < base) && (i < end))

      i++;

      while((numbers[j] > base) && (j > start))

      j--;

      if(i <= j) {

      temp = numbers[i];

      numbers[i] = numbers[j];

      numbers[j] = temp;

      i++;

      j--;

      }

      }while(i <= j);

      if(start < j)

      quickSort(numbers, start, j);

      if(end > i)

      quickSort(numbers, i, end);

      }

      }

      /**

      * 选择排序

      *

      在未排序序列中找到最小元素,存放到排序序列的起始位置

      *

      再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。

      *

      以此类推,直到所有元素均排序完毕。

      *

      *@paramnumbers

      */

      public static voidselectSort(int[] numbers) {

      intsize = numbers.length, temp;

      for(inti =0; i < size; i++) {

      intk = i;

      for(intj = size -1; j >i; j--)  {

      if(numbers[j] < numbers[k])  k = j;

      }

      temp = numbers[i];

      numbers[i] = numbers[k];

      numbers[k] = temp;

      }

      }

      /**

      * 插入排序

      *

        *

        从第一个元素开始,该元素可以认为已经被排序

        *

        取出下一个元素,在已经排序的元素序列中从后向前扫描

        *

        如果该元素(已排序)大于新元素,将该元素移到下一位置

        *

        重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

        *

        将新元素插入到该位置中

        *

        重复步骤2

        *

        *

        *@paramnumbers

        */

        public static voidinsertSort(int[] numbers) {

        intsize = numbers.length, temp, j;

        for(inti=1; i

        temp = numbers[i];

        for(j = i; j >0&& temp < numbers[j-1]; j--)

        numbers[j] = numbers[j-1];

        numbers[j] = temp;

        }

        }

        /**

        * 归并排序

        *

          *

          申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

          *

          设定两个指针,最初位置分别为两个已经排序序列的起始位置

          *

          比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

          *

          重复步骤3直到某一指针达到序列尾

          *

          将另一序列剩下的所有元素直接复制到合并序列尾

          *

          *

          *@paramnumbers

          */

          public static voidmergeSort(int[] numbers,intleft,intright) {

          intt =1;// 每组元素个数

          intsize = right - left +1;

          while(t < size) {

          ints = t;// 本次循环每组元素个数

          t =2* s;

          inti = left;

          while(i + (t -1) < size) {

          merge(numbers, i, i + (s -1), i + (t -1));

          i += t;

          }

          if(i + (s -1) < right)

          merge(numbers, i, i + (s -1), right);

          }

          }

          /**

          * 归并算法实现

          *

          *@paramdata

          *@paramp

          *@paramq

          *@paramr

          */

          private static voidmerge(int[] data,intp,intq,intr) {

          int[] B =new int[data.length];

          ints = p;

          intt = q +1;

          intk = p;

          while(s <= q && t <= r) {

          if(data[s] <= data[t]) {

          B[k] = data[s];

          s++;

          }else{

          B[k] = data[t];

          t++;

          }

          k++;

          }

          if(s == q +1)

          B[k++] = data[t++];

          else

          B[k++] = data[s++];

          for(inti = p; i <= r; i++)

          data[i] = B[i];

          }

          相关文章

            网友评论

                本文标题:数组排序

                本文链接:https://www.haomeiwen.com/subject/imnelxtx.html