排序算法

给定一个数组a[n]
1.插入排序:a[0]是已排序好的数组，对a[1]~a[n-1]依次循环，a[i]时,a[i]与之前的所有元素进行一一比较，若该元素大于a[i]，则该元素后移一位，以此类推。

void InsertSort(int a[], int n)//直接插入排序
{
    int i, j;
    for (i = 1; i < n; i++)
    {
        //int temp=a[i];
        j = i-1;
        while (j >= 0 && a[j] > a[i])
        {
            a[j + 1] = a[j];//从后向前，即把元素后移一位
            j--;
        }
        a[j + 1] = a[i];
    }
}

2.希尔排序：也是直接插入排序的一种排序，对于取gap大小的步长的每个小组进行插入排序，当gap等于1时再进行插入排序后，整个数组是有序的，这个算法相对于直接插入排序减少了元素移动的次数。

void ShellSort(int a[], int n)
{
    int i, j, gap;
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        for (i = 1; i < n; i++)     //这层循环是个直接插入排序算法
        {
            j = i - gap;
            while (j > 0 && a[j] > a[i])
            {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = a[i];
        }
    }
}

3.选择排序：每次都找出数组中最小的，并放在已排序好的数组的最后面，但是与冒泡排序有所不同，冒泡排序几乎每次都要交换相邻两个元素的位置

void SelectSort(int a[], int n)
{
    int i, j, minIndex;
    for (i = 0; i < n - 1; i++)
    {
        minIndex = i;
        for (j = i + 1; j < n; j++)
        {
            if (a[j] < a[minIndex])
            {
                minIndex = j;
            }
        }
        int temp = a[i];
        a[i]=a[minIndex];
        a[minIndex] = temp;
    }
}

4.冒泡排序：每次循环都找到最大的，并放在数组的最后；

void BubbleSort(int a[],int n)
{
    int work = 1;
    for (int i = 0; i < n - 1; i++)
    {
        work = 0;
        for (int j = 0; j < n - 1 - i; j++)//每次把最大的放后面,第一次是放最后一个，第二次是放倒数第二个，依次。
        {
            if (a[j] > a[j + 1])
            {
                Swap(a[j], a[j + 1]);
                work = 1;
            }
        }
        if (work == 0)
            break;
    }
}

5.基数排序：根据最大数的的位数为循环次数，然后依次比较个位数，十位数……，最后即为排序好的数组。

int GetMaxBits(int a[], int n)//得到数组中的最大数的位数,如100的位数为3
{
    int max = a[0],count=0;
    for (int i = 1; i < n; i++)
    {
        if (max < a[i])
            max = a[i];
    }
    while (max)
    {
        count++;
        max /= 10;
    }
    return count;
}
void RadixSort(int a[], int n)//基数排序
{
    queue<int> q[10];//10个桶(队列型的)
    int k,key = GetMaxBits(a,n),temp;
    k = key;
    while (key!=0)//最大数是几位数就执行多次循环
    {
        int j = 0;
        for (int i = 0; i < n; i++)//装入各个桶
        {
            temp = a[i];
            temp /= int(pow(10, k-key));//最大数是有三位的话，pow(10, k-key)第一次为1，第二次为10，第三次100。因为第一次比较的是个位数，第二次是十位数
            q[temp%10].push(a[i]);//根据余数入队
        }
        for (int i = 0; i < 10; i++)//把各个桶中的数据存回数组
        {
            while (!q[i].empty())
            {
                    a[j] = q[i].front();
                    q[i].pop();//队列先进先出
                    j++;
            }
        }
        key--;
    }
}

6.堆排序:构建大根堆

void HeadAdjust(int a[], int s, int n)//n为要调整的结点个数,s为要调整的结点位置
{
    int temp;
    temp = a[s];
    for (int i = 2 * s + 1; i <= n - 1; i = 2 * i + 1)//从s这个点开始往下构建大根堆二叉树
    {
        if (i < n - 1 && a[i] < a[i + 1])
        {
            i++;
        }
        if (temp >= a[i])
            break;
        a[s] = a[i];//把最大的元素往上挪
        s = i;//以i这个位置的子树重新调整
    }
    a[s] = temp;
}
void HeadSort(int a[],int n)
{
    for (int i = n / 2-1; i >= 0; i--)//构建大根堆二叉树，从最后一颗子树开始
    {
        HeadAdjust(a, i, n);//调整大根堆
    }
    for (int i = n - 1; i >= 0; i--)
    {
        Swap(a[i], a[0]);//最后一个和根互换
        HeadAdjust(a, 0, i);
    }
}

7.快速排序：需要基准点

void QuickSort(int a[],int low,int high)/*对a[low]至a[high]的元素进行快速排序*/
{
    int temp, origin_low = low, origin_high = high;
    if (low < high)        /*区间内至少存在一个元素的情况*/
    {
        temp = a[low];     /*用区间的第1个记录作为基准*/
        while (low < high)  /*从两端交替向中间扫描,直至low=high为止*/
        {
            //在数组的右端扫描[A]
            while (low < high && temp <= a[high])
            {
                high--;
            }
            a[low] = a[high];//temp>a[high]则换位置

            //在数组的左端扫描[C]
            while (low < high && a[low] < temp)
            {
                low++;
            }
            a[high] = a[low];
        }
        a[low] = temp;//基准点
        QuickSort(a, origin_low, low - 1);      /*对左区间递归排序*/
        QuickSort(a, low + 1, origin_high);     /*对右区间递归排序*/
    }
}

第k大的元素:
(从大到小的排序)

int partion(vector<int>& nums, int low, int high, int k)
{
    int index = qsort(nums, low, high);
    if (index == k) {
        return index;
    }
    else if (index>k) {
        return(partion(nums, low, index - 1, k));
    }
    else {
        return(partion(nums, index + 1, high, k));
    }
}
int  Qsort(vector<int>& nums, int low, int high)
{
    int temp = nums[low];
    while (low<high)
    {
        while (low<high)
        {
            if (temp<nums[high])
            {
                nums[low] = nums[high];
                low++;
                break;
            }
            high--;
        }
        while (low<high)
        {
            if (nums[low]<temp)
            {
                nums[high] = nums[low];
                high--;
                break;
            }
            low++;
        }
    }
    nums[low] = temp;
    return low;
}
int kthLargestElement(int k, int[] nums)
{
    return (nums[partion(nums, 0, nums.size() - 1, k - 1)]);
}