sort排序算法大总结

参考网站：http://www.runoob.com/w3cnote/sort-algorithm-summary.html

冒泡排序：babble sort O(n^2)

• 基本思想：
  两个数比较，每次选取最小的上浮，一次上浮，只排序一个数。

int* bubbleSort(int a[], int length)
{
    int temp;
    for (int i = 0; i < length-1; i++)
    {
        for (int j = 0; j < length-i-1; j++)
        {
            if (a[j]>a[j+1])
            {
                temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
        }
    }
    return a;
}

选择排序：selection sort O(n^2)

• 基本思想：和上面冒泡排序差不多，就是找到最小的位置和第一个目标数字交换

插入排序：babble sort O(n^2)

• 基本思想： 假设前面是已经排好序的，插入目标数字。每次插入都会影响后面数字往后搓一位。
  c++:

int* insertSort(int a[], int length)
{
    if (length <= 0 ||a==NULL)
    {
        cout << "wrong input" << endl;
        return NULL;
    }
    else if (length == 1)
    {
        return a;
    }
    else
    {
        int j,i,temp;
        for (i = 1; i < length; i++)
        {
            temp = a[i];
            
            for (j = i-1; j >=0&&a[j]>temp; j--)
            {
                a[j+1] = a[j];
            }
            a[j + 1] = temp;

        }
    }
    return a;
}

希尔排序：Shell sort O(n^1.5)

• 基本思想：这个我也是不太熟，需要查一下资料。主要是分组排序，每组数字的个数一次增长：2 4 8

  
  图片.png

快速排序：quick sort O(N*logN)

• 基本思想：分为两部分：
  1 找到pivot：使得左边的数字都想与目标数字，右边的大于目标数字。
  2 找到中间位置后，数组或vector就分为两部分，再次进行相同操作

  
  图片.png

//快速排序
int partition(vector<int>& nums, int low, int high) {
    int start = nums[low];
    while (low < high) {
        while (low<high&& nums[high]>start)
            high--;
        if (low < high) {
            swap(nums[low], nums[high]);
            low++;
        }
        while (low < high&&nums[low] < start)
            low++;
        if (low < high) {
            swap(nums[low], nums[high]);
            high--;
        }
    }
    nums[low] = start;
    return low;
}
void Quick(vector<int>& nums, int low, int high) {
    if (low >= high)
        return;
    int idx = partition(nums,low,high);
    Quick(nums, low, idx - 1);
    Quick(nums, idx + 1, high);
}
vector<int> QS(vector<int>& nums, int low, int high) {
    if (nums.size() == 0)
        return {};
    Quick(nums, low, high);
    return nums;
}

归并排序：Merge sort O(N*logN)

• 基本思想:

  
  图片.png
  

  C++:

//mergeSort
void Merge(vector<int>& nums, int low, int high) {
    int mid = (low + high) / 2;
    vector<int> left(mid+1), right(high+1);
    for (int i = low; i <= mid; i++)
        left[i]=nums[i];
    for (int i = mid + 1; i <= high; i++)
        right[i]=nums[i];

    int i = low, j = mid+1, idx = low;
    while (i <= mid && j<=high) {//right-->j
        if (right[j]<left[i]) {
            nums[idx++] = right[j++];
        }
        else {
            nums[idx++] = left[i++];
        }
    }
    while (i <= mid) {
        nums[idx++] = left[i++];
    }
    while (j<=high) {
        nums[idx++] = right[j++];
    }
}
void MergeS(vector<int>& nums, int low, int high) {
    if (low >= high)
        return;
    int mid = (low + high) / 2;

    MergeS(nums, low, mid);
    MergeS(nums, mid + 1, high);
    Merge(nums, low, high);
}
vector<int> MS(vector<int>& nums, int low, int high) {
    if (nums.size() == 0)
        return {};
    MergeS(nums, low, high);
    return nums;
}

堆排序：Heap sort O(N*logN)

• 基本思想：构建堆+向下调整

基数排序：babble sort O(n+r)

• 基本思想：如果数字范围是1_{100，链表头1}10：
  图片.png