排序算法 - 简书

1、选择排序
从数组第一个开始：i=0
将数组中第 i 个当作最小，保存最小值的数组下标：minPos=i
在剩余的数中，逐个（a[ j ]）来和 a[minPos] 对比，小的话，将数组下标值保存： minPos=j
经过循环之后，minPos保存着第 i 趟之后数组剩余值中最小的值的数组下标值
将 a[minPos] 中的值和 a[i] 中的值调换

/**选择排序
 *遍历数组  然后每次遍历到一个元素之后  继续遍历该元素之后的所有元素 然后找         到最小的元素 和其换位置*/
    public static int[] select(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minPos = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minPos]){
                    minPos = j;
                }
            }


            if (array[i] > array[minPos]){
                int temp = array[i];
                array[i] = array[minPos];
                array[minPos] = temp;
            }

        }
        return array;

    }

2、插入排序
同样逐个遍历数组,
每次第 i 个值和前一个值对比，第 i 个值小的话往前挪，第 i -1（-2、-3、-4）个值往后挪，因为从头开始排序,所以前面拍完的值都是按大小拍的，因此只要第 i 个值大于第 i -1个值，说明都比前面大。

 /***插入排序
     *相当于  从0开始一直++  然后一直排列索引跟之前的元素
     * */
    public static int[] insert(int[] array){
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            for (int j = i - 1; j >= 0 ; j--) {
                if (array[j] > temp ){
                    array[j + 1] = array[j];
                    array[j] = temp;
                }

            }

        }
        return array;
    }

3、快速排序
在快排中要设定分水岭就是随机一个元素，一般为数组第一个值然后比他小的放置到其左边比其大的在有边
设定两个游标，左边开始的为low，右边开始的为high（length-1）
首先从右边开始，high不断-1，直到遇到比base小的，和base交换，然后左边开始，low不断+1，直到遇到比base大的，和base交换，一直循环到 low=high ，第一次排序完成，以这个相等的这个下标值为分界线，两边各自进行之前的操作，直到拍完

/**快速排序
     * 在快排中要设定分水岭 就是随机一个元素  然后比他小的放置到其左边 比其大的在有边 循环往复
     * */
    public static int[] quick(int[] array){

        int length = array.length - 1;
        sortQuick(array,0,length);

        return array;
    }

    private static void sortQuick(int[] array, int low, int length) {
        if(low < length){
            int div = firstRun(array, low, length);
            sortQuick(array,0,div - 1);
            sortQuick(array,div + 1,length);
        }
    }

    private static int firstRun(int[] array, int low, int length) {
        int base = array[low];

        while (low < length){
            while (array[length] > base){
                length--;
            }
            swrap(array,low,length);
            while (array[low] < base){
                low++;
            }
            swrap(array,low,length);
        }
        return low;
    }

    private static void swrap(int[] array, int low, int length) {
        int temp = array[length];
        array[length] = array[low];
        array[low] = temp;
        //return array;
    }

4、合并排序
合并排序就是将数组一直拆分，将数组从中间拆分，左右数组各自递归拆分，直到拆到最后，在开始合并，合并的时候，先创建一个左右数组长度相加的长度数组，将左右两数组从各自左边开始，小的添加到新数组，并且该数组下标+1，直到其中一个数组添加完毕，将另外一个数组剩余值全部加进去。

 /**合并排序
     * 一直在分割
     * 然后 两部分 一直分割  然后一直递归*/
    public static int[] mesh(int[] array){
        int length = array.length - 1 ;
        int[] mysort = mysort(array, 0, length);
        return mysort;

    }

    private static int[] mysort(int[] array, int low, int length) {
        int mid = (length + low)/2;
        if (low < length){
            mysort(array,low,mid);
            mysort(array,mid + 1,length);
            merge(array,low,mid,length);
        }
        return array;

    }

    private static void merge(int[] array, int low, int mid, int length) {
        int[] temp = new int[length - low + 1];

        int i = low;
        int j = mid + 1;
        int n = 0;
        while (i <= mid && j <= length){
            if (array[i] > array[j]){
                temp[n++] = array[j++];
            }else {
                temp[n++] = array[i++];
            }
        }

        while (i <= mid){
            temp[n++] = array[i++];
        }


        while (j <= length){
            temp[n++] = array[j++];
        }


        //合并的逻辑  赋值给array

        for (int k = 0; k < temp.length; k++) {
            array[low + k] = temp[k];
        }


    }

5、堆排序
数组： a
范围：0~n
首先建堆，从数组中间元素开始到第一个，建立一个每个树都是大堆或者小堆
然后循环：从最后一个元素到以一个元素
将a[i]，和a[0]交换
从a[i]开始到a[0]建堆

void AdjustDown(int arr[], int i, int n)
{
    int j = i * 2 + 1;//子节点 
    while (j<n)
    {
        if (j+1<n && arr[j] > arr[j + 1])//子节点中找较小的
        {
            j++;
        }
        if (arr[i] < arr[j])
        {
            break;
        }
        swap(arr[i],arr[j]);
        i = j;
        j = i * 2 + 1;
    }
}
void MakeHeap(int arr[], int n)//建堆
{
    int i = 0;
    for (i = n / 2 - 1; i >= 0; i--)//((n-1)*2)+1 =n/2-1
    {
        AdjustDown(arr, i, n);
    }
}
void HeapSort(int arr[],int len)
{
    int i = 0;
    MakeHeap(arr, len);
    for (i = len - 1; i >= 0; i--)
    {
        swap(arr[i], arr[0]);
        AdjustDown(arr, 0, i);
    }

}

6、冒泡排序
基本思想：自下而上对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

public void bubbleSort(int[] a,int length){
    int temp;
     for(int i=0;i<length-2;i++){
          boolean isChange=false;
          for(int j=length-1;j>i;j--){
                  if(a[ j-1 ]>a[ j ]){
                        temp=a[ j-1 ];
                         a[ j-1 ]=a[ j ];
                         a[ j ]=temp;
                         isChange=true;
                  }
           }
           if(!isChange){
                break; 
            }
     }
}

7、希尔排序
取数组长度一半的值为第一个增量，后面一直减少增量为原来的一半，四舍五入。
将数组分为一个个数组，每个数组的下标相隔增量个长度，将每个数组进行插入排序

public void shellSort(int[] a){
     int h;
     for(h=a.length/2;h>=1;h/2+h%2?0:1){
          shellInsert(a,h);
     }
}
public void shellInsert(int a,int h){
int temp;
     for(int i=0;i<=h;i++){
         for(int j=i+h;j<a.length;j+h){
             if(a[ j-h ]<a[ j ]){
                 break;
             }else{
                  temp=a[ j ];
                  int k=j-h;
                  do{
                      a[ k+h ]=a[ k ];k=k-h;
                  }while(k>=0&&a[ k ]>temp);
                 a[ k-h ]=temp;
             }
         }
     }
}