学习并记录下排序算法，方便回顾。

排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 ---|---|---|---|+++ 冒泡排序| O(n2)|O(n2)|O(1)|稳定 选择排序| O(n2)|O(n2)|O(1)|数组不稳定、链表稳定 插入排序| O(n2)|O(n2)|O(1)|稳定 快速排序| O(nlog2n) | O(n2) | O(log2n) | 不稳定 堆排序| O(nlog2n)|O(nlog2n)|O(1)|不稳定 归并排序| O(nlog2n) | O(nlog2n)|O(n)|稳定 希尔排序| O(nlog2n)|O(n2)|O(1)|不稳定 计数排序 | O(n+m)|O(n+m)|O(n+m)|稳定 桶排序 | O(n)|O(n)|O(m)|稳定 基数排序| O(k*n)|O(n2)| |稳定

  • 均按从小到大排列
  • k：代表数值中的 “数位” 个数
  • n：代表数据规模
  • m：代表数据的最大值减最小值
  • 来自：wikipedia . 排序算法

冒泡排序

N个元素进行排序，总共需要N-1趟排序，第i趟需要排序的次数为N-i。($1 \leq i \leq N-1$）

思路：

  1. 第i趟，比较前N-i-1个元素，比较相邻元素
  2. 比较第1个和第2个元素，将值小的放前面，值大的放后面
  3. 比较第2个和第3个元素，……，比较N-i次
  4. 每一趟比较都会将最大值放每一趟的最后面，实现将值大的元素冒泡到最后面【第i趟将第i大值存放到倒数第i位】
//普通冒泡排序
void BubbleSort(vector<int> &v){
    int len = v.size();
    for(int i = 0; i < len - 1; ++i){
        for(int j = 0; j < len - 1 - i; ++j){
            if (v[j] > v[j + 1])
                swap(v[j], v[j + 1]);
        }
    }
    return;
}
//优化：当有一趟比较过程中一次交换都没出现，则说明当前已经是有序状态，排序结束
void BubbleSort(vector<int> &v){
    int len = v.size();
    for(int i = 0; i < len - 1; ++i){
        bool flag = true;
        for(int j = 0; j < len - 1 - i; ++j){
            if (v[j] > v[j + 1]){
                swap(v[j], v[j + 1]);
                flag = false;
            }
        }
        if(flag)return;
    }
    return;
}
//放个参数是数组的
void BubbleSort(int *a){
    int len = sizeof a / sizeof *a;
    for(int i = 0; i < len - 1; ++i){
        for(int j = 0; j < len - 1 - i; ++j){
            if (v[j] > v[j + 1])
                swap(v[j], v[j + 1]);
        }
    }
    return;
}

选择排序

N个元素进行排序，总共需要N-1次选择，将第i次选择的结果作为第i个元素。($1 \leq i \leq N-1$）

思路：

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
  3. 以此类推，直到所有元素均排序完毕
void SelectionSort(vector<int> &v){
    int min_index, len = v.size();
    for(int i = 0; i < len - 1; ++i){
        min_index = i;
        for(int j = i + 1; j < len; ++j){
            if(v[j] < v[min_index])min_index = j;
        }
        if(i != min_index)
            swap(v[i], v[min_index]);
    }
    return;
}

插入排序

思路：

  1. 从第一个元素开始，该元素可以认定为已经被排序，其他元素均认为未排序
  2. 取下未排序的第一个元素a，在已经排序的元素序列中从后向前扫描，将扫描到的已排序元素b与a比较
    1. a > b，将a元素后移一位，b存于a原来的位置
    2. a <= b，则b已经存放于a后面，不必移位
  3. 重复第2步骤直到全部排序完成
void InsertSort(vector<int> &v){
    int len = v.size();
    for(int i = 1; i < len; ++i){
        int temp = v[i];
        for(int j = i - 1; j >= 0; --j){
            if(v[j] > temp){
                v[j + 1] = v[j];
                v[j] = temp;
            }
            else break;
        }
    }
}

快速排序

递归的思路：

  1. 选取第一个数作为基准
  2. 将比基准小的数交换到前面，比基准大的数交换到后面
  3. 对左右区间重复第2步，直到各个区间只有一个数

迭代的思路：

  1. 将需要快排的区间压栈
  2. 如果栈里的区间不为空，从栈里取出最末尾的区间
    1. 区间大小为0或1，则不进行快排
    2. 进行快排，产生两个子区间
  3. 将快排结果的两个子区间压栈
//递归
void QuickSort(vector<int> &v, int low, int high){
    if(low >= high)	//表明数据只有一个元素了，排序完成
        return;
    int first = low;
    int last = high;
    int key = v[first];
    
    while(first < last){
        //从后往前找，将小于基准的移到前面
        while(first < last && v[last] >= key)
            --last;
        //判断前面的循环是因为v[last] >= key而退出来的
        if(first < last)
            v[first++] = v[last];
        
        //从前往后找，将大于基准的移到后面
        while(first < last && v[first] <= key)
            ++first;
        //判断前面的循环是因为v[first] <= key而退出来的
        if(first < last)
            v[last--] = v[first];
    }
    //将基准归位
    v[first] = key;
    //对子区间递归
    QuickSort(v, low, first - 1);
    QuickSort(v, first + 1, high);
}

//迭代
struct Range{
    int first, last;
    Range(int f = 0, int l = 0):first(f), last(l){}
};
void QuickSort(vector<int> &v, int low, int high){
    if(low >= high)	//表明数据只有一个元素了，排序完成
        return;
    const size_t len = high - low + 1;
    Range r[len];
    int p = 0;
    r[p++] = Range(low, high);
    while(p){
        Range temp = r[--p];
        if(temp.first >= temp.last){
            continue;
        }
        int key = v[temp.first];
        int left = temp.first, right = temp.last;
        while(left < right){
            while(left < right && v[right] > key)
                --right;
            while(left < right && v[left] < key)
                ++left;
            if(left < right){
                swap(v[left], v[right]);
                --right;
                ++left;
            }
        }
        if(v[temp.first] >= v[left])
            swap(v[temp.first], v[left]);
        else
            --left;
        r[p++] = Range(temp.first, left - 1);
        r[p++] = Range(left + 1, temp.last);
    }
}

堆排序

最大堆：

  1. 构建堆
    1. 从最后一个父节点开始调整，调整为符合规则的堆
    2. 从最后一个父节点递减，将所有父节点从后向前进行调整
    3. 调整到父节点为根节点则调整完毕
  2. 根据堆的特性：根节点存放最大值或最小值。将根节点与堆最后一个元素交换，并将堆的大小减一进行堆适应，重新调整为一个规则的堆
  3. 取出的元素按相反的顺序排列，完成排序
//堆适应，使堆按规则存放
void AdjustHeap(vector<int> &v, int hole, int len){
    //const int parent = hole;
    int value = v[hole];
    int right = 2 * hole + 2;
    while(right < len){
        if(v[right] < v[right-1])
            --right;
        if(v[hole] < v[right]){
            swap(v[hole], v[right]);
            hole = right;
            right = 2 * hole + 2;
        }
        else return;
    }
    if(right == len){
        if(v[hole] < v[right - 1]){
            swap(v[hole], v[right - 1]);
            hole = right - 1;
            v[hole] = value;
        }
        else return;
    }
    return;
}
//构建堆
void MakeHeap(vector<int> &v){
    int len = v.size();
    cout << len << endl;
    if(len < 2)return;
    int parent = (len - 2)/2;
    while(true){
        AdjustHeap(v, parent, len);
        if(parent == 0)return;
        parent--;
    }
    return;
}
//堆排序，逐个取出根节点
void HeapSort(vector<int> &v){
    int len = v.size();
    for(int i = len - 1; i > 0; i--){
        swap(v[0], v[i]);
        AdjustHeap(v, 0, i);
    }
    return;
}

归并排序

递归思路：

  1. 分解：将n个元素分成2个子序列
  2. 解决：对两个子序列进行归并排序，回归后得到两个有序的子序列
    1. 回归点：begin >= end，即子序列的元素个数为1后，经排序，返回有序的元素个数为2的子序列
  3. 合并：将两个有序的子序列合并，得到有序序列（有序子序列才可顺利合并）

迭代思路：

  1. 通过设置区间，模仿递归到底层再回归的过程，区间大小从小到大，直接合并、回归
//递归
void MergeSort(vector<int> &v, vector<int> &ans, int begin, int end){
    if(begin >= end)
        return;
    int len = end - begin;
    int mid = (len >> 1) + begin;
    int start1 = begin, start2 = mid;
    MergeSort(v, ans, start1, mid);
    MergeSort(v, ans, start2, end);
    int index = begin;
    while(start1 < mid && start2 < end)
        ans[index++] = v[start1] < v[start2] ? v[start1++] : v[start2++];
    while(start1 < mid)
        ans[index++] = v[start1++];
    while(start2 < end)
        ans[index++] = v[start2++];
}
//迭代
void MergeSort(vector<int> &v, vector<int> &ans, int begin, int end){
	int len = end - begin;
    for(int range = 1; range < len - 1; range << 1){
        for(int start = 0; start < len - range; start += (2 * range)){
            int mid = start + range, end = start + range + range;
            int index = start;	//使用下标读写ans，必须确保ans初始化大小和v一样
            int start1 = start, start2 = mid;	//[start, end)
            while(start1 < mid && start2 < end)
                ans[index++] = v[start1] < v[start2] ? v[start1++] : v[start2++];
            while(start1 < mid)
                ans[index++] = v[start1++];
            while(start2 < end)
                ans[index++] = v[start2++];
        }
    }
}

希尔排序

思路：

  1. 按一定步长进行插入排序，步长逐渐减小，最终为1
  2. 步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作
  3. 当步长为1时，算法变为插入排序，这就保证了数据一定会被排序
  4. 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能，交换不相邻的元素以对数组的局部进行排序，最终用插入排序将局部有序的数组排序。
//wikipedia解法，对其步长计算没理解
void ShellSort(vector<int> &v){
	int len = v.size();
    int h = 1;
    while(h < len/3)
        h = 3 * h + 1;
    while(h >= 1){
        for(int i = h; i < length; i++){
            for(int j = i; j >= h && v[j] < v[j - h]; j -= h)
                swap(v[j], v[j - h]);
        }
        h = h / 3;
    }
}

//步长为排序个数折半，步长折半减小，最终必须为1
void ShellSort(vector<int> &v){
	int len = v.size();
    for(int h = len >> 1; h > 0; h >>=1){
        for(int i = h; i < len; i++){
            for(int j = i; j >= h && v[j] < v[j - h]; j -= h)
                swap(v[j], v[j - h]);
        }
    }
}

计数排序

计数排序：统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。

计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。 如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。 计数排序不是比较排序，排序的速度快于任何比较排序算法。 时间复杂度为 O（n+k），空间复杂度为 O（n+k）

思路：

  1. 找出无序序列v的最大和最小元素
  2. 创建次数数组vCount，对无序序列的元素出现的次数进行统计
  3. 对计数进行累加，从次数数组的头开始，每一项和前一项相加，此时次数数组的值就是该元素在有序数组中的位置
  4. 反向填充有序数组ans，将每个元素i放在ans的第vCount[i]项（从1开始算）
void CountSort(vector<int> &v, vector<int> &ans){
    int len = v.size();
    if(!len)return;	// 确保待排序容器非空
    
    // 使用 v 的最大值 + 1 作为计数容器 vCount 的大小
    int vCountLength = (*max_element(v.begin, v.end)) + 1;
    vector<int> vCount(vCountLength, 0);
    
    // 统计每个键值出现的次数
    for(int i = 0; i < len; i++)
        ++vCount[v[i]];
    
    // 后面的键值出现的位置为前面所有键值出现的次数之和
    for(int i = 1; i < vCountLength; i++)
        vCount[i] += vCount[i - 1];
    
    // 将键值放到目标位置
    for(int i = len - 1; i >= 0; i--)	// 此处逆序是为了保持相同键值的稳定性
        ans[--vCount[v[i]]] = v[i];
}

//优化，待排序数组数量不多，但是数值大:对vCount大小进行精确设置，对v[i]稍加处理后才作为vCount下标
void CountSort(vector<int> &v, vector<int> &ans){
    int len = v.size();
    if(!len)return;	// 确保待排序容器非空
    
    // 使用 v 的最大值 + 1 作为计数容器 vCount 的大小
    int max = *max_element(v.begin, v.end);
    int min = *min_element(v.begin, b.end);
    int vCountLength = max - min + 1;
    vector<int> vCount(vCountLength, 0);
    
    // 统计每个键值出现的次数
    for(int i = 0; i < len; i++)
        ++vCount[v[i]-min];
    
    // 后面的键值出现的位置为前面所有键值出现的次数之和
    for(int i = 1; i < vCountLength; i++)
        vCount[i] += vCount[i - 1];
    
    // 将键值放到目标位置
    for(int i = len - 1; i >= 0; i--)	// 此处逆序是为了保持相同键值的稳定性
        ans[--vCount[v[i] - min]] = v[i];
}

桶排序

桶排序：将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。 思路：

  1. 设置一个定量的数组当作空桶子
  2. 寻访序列，把元素放到对应的桶内的同时执行插入排序，保持桶内元素有序
  3. 对每个桶进行合并，前提是桶内有序
  4. 将桶内数据倒出来，此时数据已经是排序好的
const in BUCKET_NUM = 10;	//假设数据分布在[0，100)之间

struct ListNode{
    explicit ListNode(int i = 0):data(i), next(nullptr){}
    ListNode *next;
    int data;
}
ListNode* InsertBucket(ListNode *head, int val){
    ListNode temp, new_node(val);
    temp.next = head;
    ListNode *pre = &temp, *cur = head;
    while(!cur && cur -> data <= val){
        pre = cur;
        cur = cur -> next;
    }
    new_node.next = cur;
    pre -> next = &new_node;
    return temp.next;
}

ListNode* MergeBucket(ListNode *head1, ListNode *head2){
    ListNode merge;
    while(!head1 && !head2){
        if(head1 -> data <= head2 -> data){
            merge.next = head1;
            head1 = head1 -> next;
        }
        else {
            merge.next = head2;
            head2 = head2 -> next;
        }
        merge = merge.next;
    }
    if(!head1)merge.next = head1;
    if(!head2)merge.next = head2;
    
    return merge.next;
}

void BucketSort(vector<int> &v){
    vector<ListNode*> buckets(BUCKET_NUM, 0);
    int len = v.size();
    for(int i = 0; i < len; ++i){
        int index = v[i]/BUCKET_NUM;
        ListNode *head = buckets[index];
        buciets[index] = InsertBucket(head, v[i]);
    }
    ListNode *head = buckets[0];
    for(int i = 1; i < BUCKET_NUM; ++i)
        head = MergeBucket(head, buckets[i]);
    for(auto i : v){
        i = head -> data;
        head = head -> next;
    }
}

基数排序

int MaxBit(int m){	//计算最大元素的位数
    int max_bit = 1;
    int p  = 10;
    while(m >= p){
        m /= 10;
        ++max_bit;
    }
    return max_bit;
}
void RadixSort(vector<int> &v){
    int max_bit = MaxBit(*max_element(v.begin(), v.end()));
    int len = v.size();
    vector<int> temp(len, 0);	//存放每次按位排序后的结果
    int radix = 1;				//从右向左数，第1位，按位排序
    for(int i = 1; i <= max_bit; ++i){
        vector<int> count(10, 0);
        
        //类似计数排序，按位进行计数排序
        for(int j = 0; j < len; ++j){
            ++count[(v[j]/radix) % 10];
        }
        for(int j = 1; j < 10; ++j){
            count[j] += count[j-1];
        }
        for(int j = n-1; j>=0; --j){
            temp[--count[(v[j]/radix) % 10]] = v[j];
        }
        v = tmp;
        radix *= 10;	//对排序的位数进行更新
    }
}