基本排序算法

排序算法

排序算法是计算机科学中的重要概念，用于将一组数据按照特定规则进行排序。下面是对一些常见排序算法的简要总结：

1. 冒泡排序（Bubble Sort）：比较相邻元素并交换，每次循环将最大（或最小）的元素冒泡到最后（或最前）。时间复杂度为O(n^2)。

2. 选择排序（Selection Sort）：在未排序部分找到最小（或最大）的元素，然后放置到已排序部分的末尾。时间复杂度为O(n^2)。

3. 插入排序（Insertion Sort）：将未排序元素逐个插入到已排序部分的正确位置。时间复杂度为O(n^2)，但对于近乎有序的数据效果较好。

4. 快速排序（Quick Sort）：选择一个基准元素，将小于基准的元素放在左边，大于基准的元素放在右边，然后对左右子数组分别递归应用快速排序。平均时间复杂度为O(nlogn)，最坏情况下为O(n^2)。

5. 归并排序（Merge Sort）：将数组递归地分成两个子数组，分别进行排序，然后将排好序的子数组合并成一个有序数组。时间复杂度为O(nlogn)，但需要额外的空间来存储临时数组。

6. 堆排序（Heap Sort）：将待排序数组构建为最大堆（或最小堆），然后将堆顶元素与最后一个元素交换，重复这个过程直到整个数组有序。时间复杂度为O(nlogn)，具有原地排序的特点。

7. 希尔排序（Shell Sort）：通过将数组分成多个子序列进行插入排序，逐渐缩小子序列的间隔，最终完成排序。时间复杂度取决于间隔序列的选择。

8. 计数排序（Counting Sort）：对于具有确定范围的整数，统计每个元素的出现次数，然后根据计数信息将元素放回原数组中。时间复杂度为O(n+k)，其中k是元素的范围。

这些是常见的排序算法，每个算法都有自己的特点和适用场景。选择适当的排序算法取决于数据规模、数据特征以及对性能和空间要求的考虑。

插入排序

插入排序的基本思想是：将数组分为已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，然后逐步将未排序部分的元素插入到已排序部分的正确位置，直到所有元素都被插入并排序完成。

void InsertSort(vector<int> &vec, int num) {
  for(int i = 1; i < num; i++) {
    int key = vec[i];				// key为需要移动的元素，key就是插入的元素
    for(int j = i; vec[j-1] > key && j>0; j--) {
      vec[j] = vec[j-1];
    }
    vec[j] = key;
  }
}

快速排序

​ 快速排序的核心在于挑选一个组元进行排序。

int patition(vector<int> &vec, int start, int end) {
	int i = start + 1, j = end;
  int index = (rand() % (end - start + 1)) + start;			// 随机挑选一个组元
  int pivot = vec[index];
  
  swap(a[start], a[index]);
  while(true) {
    while(vec[i] <= pivot && i <= end) {
      i++;
    }
    while(vec[j] >= pivot && j > i) {
      j--;
    }
    if(i < j) {
      break;
    }
    swap(vec[i],vec[j]);
    i++;
    j--;
  }
  swap(vec[i], vec[j]);
	return j;
}

void QuickSort(vector<int> &vec, int start, int end) {
  if(start == end) {
    return;
  }
  int index = patition(vec, start, end);
  QuickSort(vec, start, index-1);
  QuickSort(vec, index+1, end);
}

归并排序

归并排序。先将数组分小再排序合并，子数组都是有序的，先递归再归并。

void Merge(vector<int>& vec, int start, int mid, int end) {
    int len = end - start + 1;
    vector<int> temp(len, 0);
    
    int i = start, j = mid + 1, k = 0;
    while(i <= mid && j <= end) {
        if(vec[i] <= vec[j]) {
            temp[k++] = vec[i++];
        } else {
            temp[k++] = vec[j++];
        }
    }

    while(i <= mid) {
        temp[k++] = vec[i++];
    }

    while(j <= end) {
        temp[k++] = vec[j++];
    }

    for(k = 0; k <= end; k++) {
        vec[start+k] = temp[k];
    }
}

void MergeSort(vector<int>& vec, int start, int end) {
    if(start >= end) {
        return;
    }
    int mid = (start+end)/2;
    MergeSort(vec, start, mid);
    MergeSort(vec, mid+1, end);
    if(vec[mid] > vec[mid+1]) {
        Merge(vec, start, mid, end);
    }
}

堆排序

先构建最大堆，再根据最大堆排序数组

void heapify(vector<int> vec, int num, int peak) {
  int largest = peak;
  int left = 2 * peak + 1;
  int right = 2 * peak + 2;
  
  while(true) {
    if(left < num && vec[left] > vec[largest]) {
      largest = left;
    }
    if(right < num && vec[right] > vec[largest]) {
      largest = right;
    }
    // 叶子节点不比根节点大就跳出循环
		if(largest == peak) {
      break;
    }
    peak = largest;
    left = 2 * peak + 1;
    right = 2 * peak + 2;
  }
}

void HeapSort(vector<int> vec, int num) {
  // 构建最大堆
  for(int i = num / 2 - 1; i >= 0; i++) {
    heapify(vec, num, i);
  }
  
  // 将堆顶元素(最大的元素)放在堆的最后面
  for(int j = len - 1; j > 0; j--) {
    swap(a[0], a[j]);
    heapify(vec, j-1, 0)
  }
}

冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

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