常见排序算法

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

public static void bubbleSort(int[] numbers)
{
    int temp = 0;
    int size = numbers.length;
    for(int i = 0 ; i < size-1; i ++)
    {
    for(int j = 0 ;j < size-1-i ; j++)
    {
        if(numbers[j] > numbers[j+1])  //交换两数位置
        {
        temp = numbers[j];
        numbers[j] = numbers[j+1];
        numbers[j+1] = temp;
        }
    }
    }
}

/**
* 快速排序查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
*
* @param numbers 带查找数组
* @param low 开始位置
* @param high 结束位置
* @return 中轴所在位置
*/

public static int getMiddle(int[] numbers, int low,int high)
{
    int temp = numbers[low]; //数组的第一个作为中轴
    while(low < high)
    {
    while(low < high && numbers[high] > temp)
    {
        high--;
    }
    numbers[low] = numbers[high];//比中轴小的记录移到低端
    while(low < high && numbers[low] < temp)
    {
        low++;
    }
    numbers[high] = numbers[low] ; //比中轴大的记录移到高端
    }
    numbers[low] = temp ; //中轴记录到尾
    return low ; // 返回中轴的位置
}

/**
*
* @param numbers 带排序数组
* @param low 开始位置
* @param high 结束位置
*/

public static void quickSort(int[] numbers,int low,int high)
{
    if(low < high)
    {
    　　int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
    　　quickSort(numbers, low, middle-1);   //对低字段表进行递归排序
    　　quickSort(numbers, middle+1, high); //对高字段表进行递归排序
    }

}

/**
* 选择排序算法
* 在未排序序列中找到最小元素，存放到排序序列的起始位置
* 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
* 以此类推，直到所有元素均排序完毕。
* @param numbers
*/
public static void selectSort(int[] numbers)
{
int size = numbers.length; //数组长度
int temp = 0 ; //中间变量

for(int i = 0 ; i < size ; i++)
{
    int k = i;   //待确定的位置
    //选择出应该在第i个位置的数
    for(int j = size -1 ; j > i ; j--)
    {
    if(numbers[j] < numbers[k])
    {
        k = j;
    }
    }
    //交换两个数
    temp = numbers[i];
    numbers[i] = numbers[k];
    numbers[k] = temp;
}
}

/**
* 插入排序
*
* 从第一个元素开始，该元素可以认为已经被排序
* 取出下一个元素，在已经排序的元素序列中从后向前扫描
* 如果该元素（已排序）大于新元素，将该元素移到下一位置
* 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
* 将新元素插入到该位置中
* 重复步骤2
* @param numbers 待排序数组
*/

public static void insertSort(int[] numbers)
{
int size = numbers.length;
int temp = 0 ;
int j =  0;

for(int i = 0 ; i < size ; i++)
{
    temp = numbers[i];
    //假如temp比前面的值小，则将前面的值后移
    for(j = i ; j > 0 && temp < numbers[j-1] ; j --)
    {
    numbers[j] = numbers[j-1];
    }
    numbers[j] = temp;
}
}

/**
* 希尔排序的原理:根据需求，如果你想要结果从大到小排列，它会首先将数组进行分组，然后将较大值移到前面，较小值
* 移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强
* 版的插入排序
* 拿数组5, 2, 8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列
* 5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较
* 此例子是按照从大到小排列，所以大的会排在前面，第一次排序后数组为9, 2, 8, 5, 1, 3，4
* 第一次后increment的值变为3/2=1,此时对数组进行插入排序，
* 实现数组从大到小排
*/

    public static void shellSort(int[] data) 
    {
        int j = 0;
        int temp = 0;
        //每次将步长缩短为原来的一半
        for (int increment = data.length / 2; increment > 0; increment /= 2)
        {
        for (int i = increment; i < data.length; i++) 
        {
            temp = data[i];
            for (j = i; j >= increment; j -= increment) 
            {
            if(temp > data[j - increment])//如想从小到大排只需修改这里
            {   
                data[j] = data[j - increment];
            }
            else
            {
                break;
            }
            
            } 
            data[j] = temp;
        }
    
        }
    }

/**
* 归并排序
* 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
* 时间复杂度为O(nlogn)
* 稳定排序方式
* @param nums 待排序数组
* @return 输出有序数组
*/

    public static int[] sort(int[] nums, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            sort(nums, low, mid);
            // 右边
            sort(nums, mid + 1, high);
            // 左右归并
            merge(nums, low, mid, high);
        }
        return nums;
    }

/**
 * 将数组中low到high位置的数进行排序
 * @param nums 待排序数组
 * @param low 待排的开始位置
 * @param mid 待排中间位置
 * @param high 待排结束位置
 */
public static void merge(int[] nums, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;// 左指针
    int j = mid + 1;// 右指针
    int k = 0;

    // 把较小的数先移到新数组中
    while (i <= mid && j <= high) {
        if (nums[i] < nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }

    // 把左边剩余的数移入数组
    while (i <= mid) {
        temp[k++] = nums[i++];
    }

    // 把右边边剩余的数移入数组
    while (j <= high) {
        temp[k++] = nums[j++];
    }

    // 把新数组中的数覆盖nums数组
    for (int k2 = 0; k2 < temp.length; k2++) {
        nums[k2 + low] = temp[k2];
    }
}

//堆排序

#include <stdio.h>
int h[ 101];//用来存放堆的数组
int n;//用来存储堆中元素的个数，也就是堆的大小


//交换函数，用来交换堆中的两个元素的值
void swap(int x,int y)
{
    int t;
    t=h[ x];
    h[ x]=h[ y];
    h[ y]=t;
}


//向下调整函数
void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整
{
    int t,flag=0;//flag用来标记是否需要继续向下调整
    //当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行
    while( i*2<=n && flag==0 )
    {        
        //首先判断他和他左儿子的关系，并用t记录值较大的结点编号
        if( h[ i] < h[ i*2] )
            t=i*2;
        else
            t=i;
        //如果他有右儿子的情况下，再对右儿子进行讨论
        if(i*2+1 <= n)
        {
            //如果右儿子的值更大，更新较小的结点编号  
            if(h[ t] < h[ i*2+1])
                t=i*2+1;
        }
        //如果发现最大的结点编号不是自己，说明子结点中有比父结点更大的  
        if(t!=i)
        {
            swap(t,i);//交换它们，注意swap函数需要自己来写
            i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整
        }
        else
            flag=1;//则否说明当前的父结点已经比两个子结点都要大了，不需要在进行调整了
    }
}


//建立堆的函数
void creat()
{
    int i;
    //从最后一个非叶结点到第1个结点依次进行向上调整
    for(i=n/2;i>=1;i--)
    {
        siftdown(i);
    }  
}


//堆排序
void heapsort()
{
        while(n>1)
    {
                swap(1,n);
        n--;
        siftdown(1);
    }
}