数据结构：排序的总结_数据结构排序总结

排序的分类：

  内部排序：指将需要处理的所有数据加载到内部存储器中进行排序

  外部排序：数据量过大，无法加载到内存中，需要借助外部存储进行排序

冒泡排序：

public void maoPaoSort(int[] a){

    for(int i =0;i< a.length-1;i++)

    {

        boolean flag = true;

        for(int j =0;j<a.length-i-1;j++)

        {

            if(a[j]>a[j+1]) {

                int temp = a[j];

                a[j] = a[j+1];

                a[j+1] = temp;

                flag=false;

            }

        }

        if(flag) break;

    }

}

冒泡排序小结：

一共进行数组大小 - 1次 的循环。每一趟排序的次数在逐渐减少。如果我们发现在某一趟排序中，没有发生依次交换，可以提前结束冒泡排序。这就是一个优化，flag 变量做这一步。

选择排序：

public void xuanZeSort(int[] a) {

 for(int i=0;i<a.length-1;i++)

 {

     int idx=i;

     for(int j=i;j<a.length;j++)

     {

         if(a[idx]>a[j]){

             idx=j;

         }

     }

     int temp = a[idx];

     a[idx]=a[i];

     a[i]=temp;

 }

}

选择排序小结：

1.选择排序一共数组大小 -1 轮排序。

2.每 1 轮排序，又是一个循环，循环规则如下

1.先假定当前这个数是最小的。

2.然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小的数，并的到下标。

3.当遍历到数组最后时，本轮得到本轮最小的数的下标。

4.交换（看代码）

插入排序：

public void chaRuSort(int[] a) {

    for (int i = 1; i < a.length; ++ i) {

        int insertValue = a[i];

        int insertIndex = i - 1;//表示有序表的最后这个元素的下标

        //还没找到位置

        while (insertIndex >= 0 && insertValue < a[insertIndex]) {

            a[insertIndex + 1] = a[insertIndex];

            insertIndex -= 1;

        }

        //退出while循环 说明插入的位置被找到

        a[insertIndex + 1] = insertValue;

    }

}

插入排序小结：

把n个待排序的元素看成为，一个有序和一个无序表，开始时有序表中只包含一个元素，无序表中包含了n-1个元素， 排序过程中每次从无序表中取出第一个元素，把它的排序码一次与有序表元素的排序码进行比较，将它插入到有序表中的适当位子，使之称为新的有序表。

就像一手扑克牌整理成有序的。

希尔排序：

public void shellSort(int[] a) {

  for(int gap = a.length/2 ; gap>0 ; gap /=2)

  {

      for(int i=gap;i<a.length;i++)

      {

          for(int j=i-gap;j>=0;j-=gap)

          {

              if(a[j]>a[j+gap]) {

                  int temp = a[j];

                  a[j] = a[j + gap];

                  a[j+gap]=temp;

              }

          }

      }

  }

}

希尔排序小结：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的减少，每组包含的关键词越来越多，当增量减到 1 时，整个文件恰好被分成一组，使算法停止

快速排序：

public static  void quickSort(int[] a,int left,int right) {

   int l =left;

   int r=right;

   int povit=a[(left+right)/2];

   while(l<r)

   {

       while(a[l]<povit) l++;

       while(a[r]>povit) r--;

       if(l>=r)break;

       int temp = a[l];

       a[l] = a[r];

       a[r] = temp;

   }

   if(l==r)

   {

       l++;

       r--;

   }

   if(left<r) quickSort(a,left,r);

   if(right>l) quickSort(a,l,right);

}

快速排序小结：

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

归并排序：

public static void main(String[] args) {

    int[] arr = {5, 4, 3, 2, 1};

    int[] temp=new int[arr.length];

    mergeSort(arr,0, arr.length-1,temp);

    for (int i : arr) {

        System.out.println(i);

    }

}

public static  void mergeSort(int[] a,int left,int right,int[] temp) {

  if(left<right)

  {

      int mid = (left+right)/2;

      mergeSort(a,left,mid,temp);

      mergeSort(a,mid+1,right,temp);

      merge(a,left,mid,right,temp);

  }

}

public  static void  merge(int[] a,int left,int right,int mid,int[] temp)

{

    int i=left;

    int j=mid+1;

    int index=0;

    while(i<=mid&&j<=right)

    {

        if(a[i]<=a[j])

        {

            temp[index++] = a[i++];

        }

        else

        {

            temp[index++] = a[j++];

        }

    }

    while(i<=mid)

    {

        temp[index++] = a[i++];

    }

    while(j<=left)

    {

        temp[index++] = a[j++];

    }

    index = 0;

    int tempLeft = left;

    while(tempLeft<=right)

    {

        a[tempLeft++] = temp[index++];

    }

}

堆排序：

public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        creatHeap(arr);
        for(int j=arr.length-1;j>0;j--)
        {
           swap(arr,0,j);
           adjustHeap(arr,0,j);
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }

   public static void creatHeap(int[] a)
   {
       for(int i=a.length/2-1;i>=0;--i)
       {
           adjustHeap(a,i,a.length);
       }

   }

   public static void adjustHeap(int[] a,int i,int length)
   {
       int temp=a[i];
       for(int k=2*i+1;k<length;k=2*k+1)
       {
           if(k+1<length&&a[k]<a[k+1])
           {
               k++;
           }
           if(a[k]>temp)
           {
               a[i]=a[k];
               i=k;
           }
           else break;
       }
       a[i] = temp;
   }

   public static void swap(int[] a,int i,int j)
   {
       int temp = a[i];
       a[i] = a[j];
       a[j] = temp;
   }
}

堆排序小结：

将待排序序列构造成一个大(小)顶堆

此时，整个序列的最大值就是堆顶的根节点。

将其与末尾元素进行交换，此时末尾就为最大值。

然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。