十个经典的排序算法

发布于 2024-06-05  856 次阅读

十个经典的排序算法

咱们评判一个算法的指标呢，常常有以下这几种

  • 平均时间复杂度

时间复杂度，用通俗的话来说，假设有n个数据元素。一个操作(分原子操作)的时间*n

  • 空间复杂度

空间复杂度，用通俗的话来讲，还是n个数据元素，运行算法时使用的n个存储空间。

  • 排序方式

外部排序或是内部排序，外部就是需要使用到除要排序的数据存储外的还要使用的临时存储空间。

而内部，就是直接在数据存储的内存进行操作。

  • 最好情况

顾名思义，时间复杂度的

  • 最坏情况·1

顾名思义，时间复杂度的

冒泡

从头或者从尾部开始，比较相邻的两q个元素，比大小规则，满足就交换。

做完一轮，最后或者开头的元素会是最大/最小值，循环-1，继续一轮比较。如此反复。

冒泡排序

代码示范

void BubbleSort(vector<int>& arr, int size){
    for (int i = 1; i < size; i++)
    {
        for (int j = 0; j < size - i; j++)
        {
            if(arr[j] > arr[j+1]) swap(arr[j],arr[j+1]);
        }
    }
}

选择

先走一轮，先找最大，或者最小。找到了放到当前起始或结尾

再从剩余的元素找最大，或者最小。找到了放在当前起始或结尾,重复该操作。

选择排序

代码示范

void SelectSort(vector<int>& arr, int size){
      for (int i = 0; i < size-1; i++)
      {
        int min = i;
        for (int j = i + 1; j < size ; j++)
        {
            if(arr[min]>arr[j]) min = j;
        }
        if(i != min) swap(arr[i], arr[min]);   
      }

}

插入

从头或从尾，第一元素为准，然后与后方(或者前方)的一个元素比较，满足大或小的比较后，将其插入比较的第一元素的前方或后方。重复该操作

插入排序

代码示范

    for (int i = 0; i < size; i++)
    {
        int temp = arr[i];
        int j = i;
        while (j > 0 && temp < arr[j - 1])
        {
            arr[j] = arr[j - 1];
            j--;
        }
        if(j != i) arr[j] = temp;

    }

希尔

实际上是插入排序的改进版，不同的是它通过一个增量gap规则来进行插入排序。

将一个待排的数组元素，分成了gap增量组，这个gap值由数组总长/步长，假设设定步长为2 ， 总长有10，gap值 = 5；

每个组内的元素进行一次插入排序

总体排序后，然后缩小这个增量，gap = gap/步长 = 5/2 = 2,gap就为2；

每个组内的元素进行一次插入排序

总体排序后，然后缩小这个增量，gap = gap/步长 = 2/2 = 2,gap就为1；

最后只需要再执行一次插入排序就可以完成整个数组的排序。

希尔排序

代码示范

    for (int i = 0; i < size; i++)
    {
        int temp = arr[i];
        int j = i;
        while (j > 0 && temp < arr[j - 1])
        {
            arr[j] = arr[j - 1];
            j--;
        }
        if(j != i) arr[j] = temp;

    }

归并

思想其实就是分而治之。（蛮多算法其实就是这样的，比如上方的希尔排序起始分增量也算是）

对于排序，最快，最方便起始，就是有只有两个元素的比较是最快的。

归并的根本原理就是如此，就是把一组n个数的序列，折半分为两个序列，然后再将这两个序列再分，一直分下去，直到分为n个长度为1的序列。然后两两按大小归并。如此反复，直到最后形成包含n个数的一个数组。

这个反复分与治的操作，可以使用递归进行处理。

归并排序

代码示范


void merge(vector<int>& arr,int L,int mid,int R)
{
    vector<int> help(R-L+1);
    int p1=L,p2=mid+1,i=0;
    while(p1<=mid && p2<=R)
        help[i++] = arr[p1]>arr[p2] ? arr[p2++] : arr[p1++];
    while(p1<=mid)
        help[i++] = arr[p1++];
    while(p2<=R)
        help[i++] = arr[p2++];
    for (int i=0;i<R-L+1;i++) 
        arr[L+i] = help[i]; 
}
void sort(vector<int>& arr, int L, int R){
    if(L<R){
        //递归分两份，跳出递归条件为L<R
        int mid = L + ((R-L)>>1);
        sort(arr,L,mid);
        sort(arr,mid+1,R);
        merge(arr,L,mid,R);
    }
}

void MergeSort(vector<int>& arr, int size ){
    cout <<__FUNCTION__<<char(10);
    if(size < 2) return;
    sort(arr,0, size-1);
}

AC代码

const int N = 10000;
int nums[N],tmp[N];
void merge_sort(int nums[],int l,int r){
    if(l>=r) return;
    int mid=(l+r)>>1;
    merge_sort(nums,l,mid);
    merge_sort(nums,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(nums[i]<=nums[j]) tmp[k++]=nums[i++];
        else tmp[k++]=nums[j++];
    }
    while(i<=mid) tmp[k++]=nums[i++];
    while(j<=r) tmp[k++]=nums[j++];
    for(int i=l,j=0;i<=r&&j<k;i++,j++){
        nums[i]=tmp[j];
    }
}

抄ACM大佬的。

快速

也是分儿治之，一个待排的序列，我们找准一个基准数，根据这个基准数，将这个分为两份序列，一份大于基准数（等于），一份小于基准数（等于）。

同理，这两份序列（等不等长取决于你所选取的基准数在序列中排序后所处的位置.），继续执行个选取基准数规则，继续分。直到基准数左右两边都找不到符合规则需要操作的元素。

一直分一直分，最后分成两个比较，当然是最快的比较方式了。

重复的操作，当然还是用递归来实现.

快速排序

代码示范

int quick(vector<int>& arr, int L, int R){
    int p = arr[L];
    while (L<R)
    {
       while (L<R && arr[R]>p) 
            R--;
        if (L < R) swap(arr[L++], arr[R]);
        while (L < R && arr[L] <= p) 
            L++;
        if (L < R) swap(arr[L], arr[R--]);
    }
    return L;
}
void qsort(vector<int>& arr, int L, int R){
    int mid;
    if (L < R)
    {
        mid = quick(arr, L, R);  
        qsort(arr, L, mid - 1); 
        qsort(arr, mid+1, R);
    }
}
void QuickSort(vector<int>& arr, int size ){
    cout <<__FUNCTION__<<char(10);
    qsort(arr,0,size - 1);
}

AC代码

const int N = 10000;
int nums[N];
void QS(int nums[], int left, int right)
{
    if (left >= right) return;
    int record = nums[left], i = left - 1, j = right + 1;
    while (i < j)
    {
        do i++; while (nums[i] < record);
        do j--; while (nums[j] > record);
        if (i < j) std::swap(nums[i], nums[j]);
    }
    QS(nums, left, j);
    QS(nums, j + 1, right);
}

堆

构建大顶堆，通俗的来说，最大元素的放在堆顶，就是大顶堆。

完全二叉树是一种重要的树形结构类型，根据堆顶元素与字串元素的大小分为，大根堆，与小根堆。

实现问题：

  1. 如何由无序序列建成一个堆？
  2. 如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

我们从待排序列创建一个堆

有两种方法

  • 先取值，在建堆。
  • 边取值边建堆。

创建堆，选取第一个值进行创建，一第一个作为母结点也就是根，对比后续的元素大小，大于替换根，原根变为子叶结点（也可能是根），同理，利用递归就可以得到一个堆，大根堆完全二叉树。

大根堆堆排序，取出堆顶元素，最后一个非子叶结点与堆顶的两个子节点进行对比，谁大交换成为堆顶，然后继续取出堆顶元素，重复迭代，直到输出最后一个元素。

堆排序

代码示范

void heapify(vector<int> &arr, int i, int size) {
  int l = 2 * i + 1;
  int r = 2 * i + 2;
  int max = i;

  if (l < size && arr[l] > arr[max])
    max = l;
  if (r < size && arr[r] > arr[max])
    max = r;
  if (max != i) {
    swap(arr[i], arr[max]);
    heapify(arr, max, size);
  }
}
void buildheap(vector<int> &arr, int size) {
  for (int i = (int)(size / 2); i >= 0; i--) {
    heapify(arr, i, size);
  }
}
void HeapSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  buildheap(arr, size);
  for (int i = size - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    size--;
    heapify(arr, 0, size);
  }
}

计数

该算法的的基本条件满足 已知数组元素范围的数组，线性的整数。

所以需要知道该数组的最大值，最小值，自建一个[max]数组用来存储每个值出现的次数，初始化为0。比如说 25的值出现了一次，所以该数组第25加1（为了符合直觉所以+1）个元素计数加1。

最后再根据统计数组填充数组。

说实话这玩意过于简单，当数组元素范围很大，或是有很多计量等，所消耗的空间和时间都大。

计数排序

代码示范

void CountingSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  auto max = *max_element(begin(arr), end(arr));
  ssize_t countsize = max + 1;
  vector<int> result(size);
  vector<int> count(countsize);
  for (auto i : arr) {
    count[i]++;
  }
  int arrindex = 0;
  for (int i = 0; i < countsize; i++) {
    while (count[i] > 0) {
      result[arrindex++] = i;
      count[i]--;
    }
  }
  arr = result;
}

桶

其实也是分而治之的思想。

设定固定数量桶，桶数量和存储的规则可以按照数组范围大小进行一个均分。

这个规则（映射函数）分出来的桶满足线性增加。

比如说52是待排元素中最大额值，2是最小值。通达的小为5（分少了桶内的排序会耗时增加，分多了存储的规则计算耗时也增加，同时内存也会增加，需要进行权衡）。

每个桶都可以使用不同或者相同的算法进行排序（当然，继续用桶排也不是不行哈）。

桶排序

代码示范

void BucketSort(vector<int> &arr, int size, size_t bucketsize = 5) {
  cout << __FUNCTION__ << char(10);
  auto max = max_element(begin(arr), end(arr));
  auto min = min_element(begin(arr), end(arr));
  vector<int> result;
  int bucketCount = ((*max) - (*min)) / 2 + 1;
  vector<vector<int>> buckets(bucketCount);
  for (int i = 0; i < size; i++) {
    int index = (arr[i] - (*min)) / bucketsize;
    buckets[index].push_back(arr[i]);
  }
  for (int i = 0; i < bucketCount; i++) {
    if (buckets[i].size() == 0)
      continue;
    if (buckets[i].size() > 1) {
      InsertSort(buckets[i], buckets[i].size());
    }
    result.insert(result.end(), buckets[i].begin(), buckets[i].end());
  }
  arr = result;
}

基数

通过的数个十百的位的数进行排序（基数）

将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

其实本质上也是桶排，不过这个桶是固定的从0到9十个桶

先从个位找起，再从十位，逐渐往高位找。

基数排序

代码示范

void radix(vector<int> &arr, int size, int exp) {
  vector<int> result(size, 0);
  vector<int> buckets(10, 0);
  for (int i = 0; i < size; i++) {
    buckets[(arr[i] / exp) % 10]++;
  }
  for (int i = 1; i < 10; i++) {
    buckets[i] += buckets[i - 1];
  }
  for (int i = size - 1; i >= 0; i--) {
    int iexp = (arr[i] / exp) % 10;
    result[buckets[iexp] - 1] = arr[i];
    buckets[iexp]--;
  }
  arr = result;
}

void RadixSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  auto max = *max_element(begin(arr), end(arr));
  int exp = 1;
  for (; max / exp > 0; exp *= 10) {
    radix(arr, size, exp);
  }
}

十大算法演示DEMO

#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

enum SORTTYPE : int {
  Bubble = 0,
  Select,
  Insert,
  Shell,
  Merge,
  Quick,
  Heap,
  Counting,
  Bucket,
  Radix
};

void swap(int &a, int &b) {
  a ^= b;
  b ^= a;
  a ^= b;
}

void CountingSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  auto max = *max_element(begin(arr), end(arr));
  ssize_t countsize = max + 1;
  vector<int> result(size);
  vector<int> count(countsize);
  for (auto i : arr) {
    count[i]++;
  }
  int arrindex = 0;
  for (int i = 0; i < countsize; i++) {
    while (count[i] > 0) {
      result[arrindex++] = i;
      count[i]--;
    }
  }
  arr = result;
}
void radix(vector<int> &arr, int size, int exp) {
  vector<int> result(size, 0);
  vector<int> buckets(10, 0);
  for (int i = 0; i < size; i++) {
    buckets[(arr[i] / exp) % 10]++;
  }
  for (int i = 1; i < 10; i++) {
    buckets[i] += buckets[i - 1];
  }
  for (int i = size - 1; i >= 0; i--) {
    int iexp = (arr[i] / exp) % 10;
    result[buckets[iexp] - 1] = arr[i];
    buckets[iexp]--;
  }
  arr = result;
}

void RadixSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  auto max = *max_element(begin(arr), end(arr));
  int exp = 1;
  for (; max / exp > 0; exp *= 10) {
    radix(arr, size, exp);
  }
}

void merge(vector<int> &arr, int L, int mid, int R) {
  vector<int> help(R - L + 1);
  int p1 = L, p2 = mid + 1, i = 0;
  while (p1 <= mid && p2 <= R)
    help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
  while (p1 <= mid)
    help[i++] = arr[p1++];
  while (p2 <= R)
    help[i++] = arr[p2++];
  for (int i = 0; i < R - L + 1; i++)
    arr[L + i] = help[i];
}
void msort(vector<int> &arr, int L, int R) {
  if (L < R) {
    // 递归分两份，跳出递归条件为L<R
    int mid = L + ((R - L) >> 1);
    msort(arr, L, mid);
    msort(arr, mid + 1, R);
    merge(arr, L, mid, R);
  }
}

void MergeSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  if (size < 2)
    return;
  msort(arr, 0, size - 1);
}

int quick(vector<int> &arr, int L, int R) {
  int p = arr[L];
  while (L < R) {
    while (L < R && arr[R] > p)
      R--;
    if (L < R)
      swap(arr[L++], arr[R]);
    while (L < R && arr[L] <= p)
      L++;
    if (L < R)
      swap(arr[L], arr[R--]);
  }
  return L;
}
void qsort(vector<int> &arr, int L, int R) {
  int mid;
  if (L < R) {
    mid = quick(arr, L, R);
    qsort(arr, L, mid - 1);
    qsort(arr, mid + 1, R);
  }
}
void QuickSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  qsort(arr, 0, size - 1);
}

void heapify(vector<int> &arr, int i, int size) {
  int l = 2 * i + 1;
  int r = 2 * i + 2;
  int max = i;

  if (l < size && arr[l] > arr[max])
    max = l;
  if (r < size && arr[r] > arr[max])
    max = r;
  if (max != i) {
    swap(arr[i], arr[max]);
    heapify(arr, max, size);
  }
}
void buildheap(vector<int> &arr, int size) {
  for (int i = (int)(size / 2); i >= 0; i--) {
    heapify(arr, i, size);
  }
}
void HeapSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  buildheap(arr, size);
  for (int i = size - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    size--;
    heapify(arr, 0, size);
  }
}

void InsertSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  for (int i = 0; i < size; i++) {
    int temp = arr[i];
    int j = i;
    while (j > 0 && temp < arr[j - 1]) {
      arr[j] = arr[j - 1];
      j--;
    }
    if (j != i)
      arr[j] = temp;
  }
}
void ShellSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  for (int gap = size / 2; gap > 0; gap = gap / 2) {
    for (int i = 0; i < size; i++) {
      for (int j = i + gap; j < size; j += gap) {
        int temp = arr[j];
        int m = j - gap;
        for (m = j - gap; m >= 0 && arr[m] > temp; m -= gap) {
          arr[m + gap] = arr[m];
        }
        arr[m + gap] = temp;
      }
    }
  }
}

void SelectSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  for (int i = 0; i < size - 1; i++) {
    int min = i;
    for (int j = i + 1; j < size; j++) {
      if (arr[min] > arr[j])
        min = j;
    }
    if (i != min)
      swap(arr[i], arr[min]);
  }
}

void BubbleSort(vector<int> &arr, int size) {
  cout << __FUNCTION__ << char(10);
  for (int i = 1; i < size; i++) {
    for (int j = 0; j < size - i; j++) {
      if (arr[j] > arr[j + 1])
        swap(arr[j], arr[j + 1]);
    }
  }
}

void BucketSort(vector<int> &arr, int size, size_t bucketsize = 5) {
  cout << __FUNCTION__ << char(10);
  auto max = max_element(begin(arr), end(arr));
  auto min = min_element(begin(arr), end(arr));
  vector<int> result;
  int bucketCount = ((*max) - (*min)) / 2 + 1;
  vector<vector<int>> buckets(bucketCount);
  for (int i = 0; i < size; i++) {
    int index = (arr[i] - (*min)) / bucketsize;
    buckets[index].push_back(arr[i]);
  }
  for (int i = 0; i < bucketCount; i++) {
    if (buckets[i].size() == 0)
      continue;
    if (buckets[i].size() > 1) {
      InsertSort(buckets[i], buckets[i].size());
    }
    result.insert(result.end(), buckets[i].begin(), buckets[i].end());
  }
  arr = result;
}

void sort(vector<int> &arr, int size, SORTTYPE sw, int addarg = 5) {
  for (auto i : arr)
    cout << i << " ";
  cout << "\nSort:";
  switch (sw) {
  case Bubble:
    BubbleSort(arr, size);
    break;
  case Select:
    SelectSort(arr, size);
    break;
  case Insert:
    InsertSort(arr, size);
    break;
  case Shell:
    ShellSort(arr, size);
    break;
  case Merge:
    MergeSort(arr, size);
    break;
  case Quick:
    QuickSort(arr, size);
    break;
  case Heap:
    HeapSort(arr, size);
    break;
  case Counting:
    CountingSort(arr, size);
    break;
  case Bucket:
    BucketSort(arr, size, addarg);
    break;
  case Radix:
    RadixSort(arr, size);
    break;

  default:
    break;
  }
  for (auto i : arr)
    cout << i << " ";
}

int main(int argc, char *argv[]) {
  int sw;
  int argadd = 5;
  if (argc == 1) {
    cout << "0 Bubble\n"
         << "1 Select\n"
         << "2 Insert\n"
         << "3 Shell\n"
         << "4 Merge\n"
         << "5 Quick\n"
         << "6 Heap\n"
         << "7 Counting\n"
         << "8 Bucket\n"
         << "9 Radix\n";
    return 0;
  }

  if (argc == 2) {
    sw = atoi(argv[1]);
    if (sw == 8) {
      printf("Bucket defult value : %d \n", argadd);
    }
  }

  if (argc == 3) {
    sw = atoi(argv[1]);
    if (sw == 8) {
      argadd = atoi(argv[2]);
    }
  }

  vector<int> a = {1, 2, 32, 4, 8, 7, 73, 4, 3, 43, 5, 6, 59};
  int size = a.size();
  sort(a, size, (SORTTYPE)sw, argadd);
  return 0;
}