重点是快速排序和堆排序

一、冒泡排序

        思路：重复地遍历要排序的数列，若其顺序不对则将其进行交换（元素经过交换浮至数列顶端）

        特点：两层嵌套循环，循环内比较交换

public void BubbleSort(int[] arr)
{
    for(int i=0; i<arr.lenght; i++)
        for(int j=0; j<arr.lenght-1 ;j++)    //双层遍历
            if(arr[j]>arr[j+1])
            {
                int temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;    //交换
            }
}

        改进：为了减少嵌套循环内层循环的次数，可以略过已排序好的数列（表现在令内层循环的计数元素 j 每次从 i+1起）

public void BubbleSort(int[] arr)
{
    for(int i=0; i<arr.lenght; i++)
        for(int j=i; j<arr.lenght-1 ;j++)    //双层遍历
            if(arr[j]>arr[j+1])
            {
                int temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;    //交换
            }
}

二、选择排序

        选择排序可以看成是优化过的冒泡排序

        步骤如下：      ①找到最大(小)的元素

                                ②将至与第一个元素交换位置

                                ③在剩下的数组中重复①②

        与冒泡排序的区别：直接一步到位移动而不是逐个移动；交换需要在内层元素完成遍历后进行

public void ChoiceSort(int[] arr)
{
    for(int i=0; i<arr.length; i++)
    {
        int miniIndex = 0;//最小元素下标
        for(int j=i; j<arr.length; j++)
            if(arr[j]<arr[miniIndex])
                miniIndex = j;
        
        //遍历所有元素，进行交换
        int temp = arr[miniIdex];
        arr[miniIndex] = arr[i];
        arr[i] = temp;
    }
}

三、插入排序

        并不是比较交换排序，而是通过找到合适位置将元素进行插入；适合接近有序数列使用，也适用于小规模数据

        步骤如下：      ①标注需排序的元素，将其前方的序列视为已排序序列(从0开始)

                                ②将需排序的元素进行比较，找到合适的插入位置，将此位置起的所有已排序序列后移一位

                                ③将待排序元素插入到后移序列的前方

        特点：比较会在找到合适的位置终止（而不遍历整个序列）

public void InsertSort(int[] arr)
{
    int currValue;    //当前待排序元素
    for(int i=0; i < arr.length-1; i++)
    {
        int preIndex = i;//标记已被排序的序列
        currValue = arr[preIndex+1];    //赋值待排序元素
 
        //进行比较，将合适位置后的数据后移        
        while(preIndex >=0 && currVaule < arr[preIndex])
        {
            arr[preIndex +1] = arr[preIndex];
            preIndex--;
        }
 
        //后移结束，将元素插入新位置
        arr[preIndex + 1] = currValue;
    }
}

四、快速排序

        是对冒泡排序的一种改进，采用分治法

        步骤如下：      ①选取一个数据作为基准数，将大的放后面小的放前面（称为分区）

                                ②对分割的两个部分分别重复步骤①

public void QuickSort(int[] arr,int start,int end)
{
    int zoneIndex = partition(arr,start,end);//快速分割+交换
    if(zoneIndex > start)
        QuickSort(arr,start,zoneIndex-1);//半区快排
    if(zoneIndex < end)
        QuickSort(arr,zoneIndex+1 ,end);/半区快排
}
 
private int partition(int[] arr,int start,int end)
{
    if(start==end)    return start;//单个元素无需分组
    int pivot = (start + Math.random()*(end-start+1));//选取一个随机数
    int zoneIndex = start-1;
 
    swap(arr,pivot,end);//将基准数与分区尾元素交换位置
    for(int i=start;i<=end;i++)
    {
            if(arr[i]<=arr[end])//计数器+1，但无需交换
                zoneIndex++;
            if(i > zoneIndex)
                swap(arry,i,zoneIndex);//左右互换
    }
    return zoneIndex;
}

五、希尔排序

        基于插入排序，将需要排序的数组进行分组，对分组内部进行插入排序；随后将分组扩大(个数减少)再次进行插入排序，直至只剩下一个分组。

        增量（组数）选择 gap=length/2 <折半，但是不一定这么选择>

        分组：两两一组，每组成员间的下标相差gap（如图gap=7，同色元素为一组）

         随后gap=7/2=3，使用3进行分组插入排序

public void ShellSort(int[] arr)
{
    int len=arr.length;
    int currValue,gap=len/2;//获取分组步长
    while(gap>0)
    {
        for(int i =gap; i<len; i++)
        {
            currValue = arr[i];//标记当前元素
            int preIndex = i - gap;//标记组内已被排序的序列
            while(preIndex>=0 && arr[preIndex] > currValue)
            {
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex + gap] =currValue;    //while结束说明找到了合适的位置
        }
        gap /= 2;
    }
}