排序

插入排序

void InsertSort(int a[],int l)//从小到大
{
    int temp;
    int j;
    for(int i=1;i<l;i++)
    {
        if(a[i]<a[i-1])
        {
            temp=a[i];
            for(j=i-1;j>=0&&temp<a[j];j--)
            {
                a[j+1]=a[j];
            }
            a[j+1]=temp;
        }
    }
}

计数排序

//通常用于元素大小不是特别大时
vector<int> countSort(vector<int> array, int n)//从小到大
{
    // 1.得到数列的最大值与最小值，并算出差值d
    int max = array[0];
    int min = array[0];
    for (int i = 1; i < n; i++)
    {
        if (array[i] > max)
        {
            max = array[i];
        }
        if (array[i] < min)
        {
            min = array[i];
        }
    }
    int d = max - min;
    // 2.创建基于差值长度的统计数组并统计填充对应元素个数
    vector<int> countArray(d + 1);
    for (int i = 0; i < n; i++)
    {
        countArray[array[i] - min]++;
    }
    // 3.统计数组变形，后面的元素等于前面的元素之和
    for (int i = 0; i < d + 1; i++)
    {
        countArray[i] = countArray[i] + countArray[i - 1];
    }
    // 4.倒序遍历原始数组，从统计数组找到正确位置，输出到结果数组
    vector<int> sortedArray(n);
    for (int i = n - 1; i >= 0; --i)
    {
        int index = countArray[array[i] - min] - 1;
        sortedArray[index] = array[i]; // 按存取的方式取出临时数组的元素
        countArray[array[i] - min]--;  // 临时数组相应位置减1
    }
    return sortedArray;
}

归并排序

void ci(int *a, int *r, int s, int e, int *c)//从小到大
{
    int mid, i, j, k;
    if (s == e)
    {
        return;
    }
    mid = (s + e) / 2;
    ci(a, r, s, mid, c);
    ci(a, r, mid + 1, e, c);
    i = s;
    j = mid + 1;
    k = s;
    while (i <= mid && j <= e)
    {
        if (a[i] <= a[j])
        {
            r[k] = a[i];
            k++;
            i++;
        }
        else
        {
            r[k] = a[j];
            *c = *c + mid - i + 1;
            k++;
            j++;
        }
    }
    while (j <= e)
    {
        r[k] = a[j];
        k++;
        j++;
    }
    while (i <= mid)
    {
        r[k] = a[i];
        i++;
        k++;
    }
    for (i = s; i <= e; i++)
    {
        a[i] = r[i];
    }
}

快速排序

void quickSort(int nums[], int start, int end)
{
    // 数组有多个元素进行排序
    if (start < end)
    {
        int base = nums[start]; // 以要进行排序数组第0个元素为base
        int left = start;       // 左指针
        int right = end;        // 右指针
        while (left < right)
        {
            // 从右向左找，比base大，right--
            while (left < right && nums[right] >= base)
            {
                right--;
            }
            // 比base小，替换left所在位置的数字
            nums[left] = nums[right];
            // 从左向右找，比base小，left++
            while (left < right && nums[left] <= base)
            {
                left++;
            }
            // 比base大，替换right所在位置的数字
            nums[right] = nums[left];
        }
        nums[left] = base; // 此时left=right，用base替换这个位置的数字
        // 排列比base小的数字的数组
        quickSort(nums, start, left - 1);
        // 排列比base大的数字的数组
        quickSort(nums, left + 1, end);
    }
}
//qsort(a,n,sizeof(a[0]),cmp);