八大排序 (上)(含时间复杂度的分析)

void insertsort(int* a, int sz)//直接插入排序   [0 end]有序，插入end+1位置的值让[ 0 end+1]也有序
{
    int i = 0;//假设我们要排升序
    for (i = 0; i < sz - 1; i++)//i不能取到sz-1 否则tmp就会造成越界访问
    {
        int end = i;
        int tmp = a[end + 1];//后一个数据
        while (end >= 0)
        {
            if (a[end] > tmp)//如果数组中的数据大于tmp
            {
                a[end+1] = a[end];
                end--;
            }
            else
            {
                break;//找到比tmp小的就结束循环
            }
        }
        a[end + 1] = tmp;//为了防止tmp比所有数据都小这种情况发生
    }
    
}

void shellsort(int* a, int n)//希尔排序
{
    int i = 0;
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1; //间隔为gap的多组数据同时排
        for (i = 0; i < n - gap; i++)//如果gap换成1  那就是直接插入排序
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end = end - gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

void selectsort(int arr[], int n)//直接选择排序
{
    int begin = 0;
    int end = n - 1;
    while (begin < end)
    {

        int max = begin;
        int min = begin;
        int i = 0;
        for (i = begin; i <= end; i++)
        {
            if (arr[i] < arr[min])
            {
                min = i;//通过交换找到最大值坐标
            }
            if (arr[i] > arr[max])
            {
                max = i;//通过交换找到最小值坐标
            }
        }
        swap(&amp;arr[begin], &amp;arr[min]);//通过坐标将最小值交换到第begin个
        if (begin == max)
        {
            max = min;
        }
        swap(&amp;arr[end], &amp;arr[max]);//通过坐标将最大值交换到第end个
        begin++;
        end--;
    }
}

void bubblesort(int* a, int sz)
{
    int i = 0;
    int j = 0;
    for (i = 0; i < sz - 1; i++)// i代表趟数  i在倒数第二次就已经把数组排好了 
    {
        int exchange = 0;
        for (j = 0; j < sz - 1 - i; j++)//j代表每趟的对数 
        {
            if (a[j] > a[j + 1])
            {
                int tmp = 0;
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                exchange = 1;
            }
        }
        if (exchange == 0)//说明遍历一遍都没有进行比较，则有序
        {
            break;
        }
    }
}