十大排序算法汇总（基于C++）

冒泡排序

void bubbleSortUp(vector<int> &nums)
{for (int i = 0; i < nums.size() - 1; i++){bool isSwap = false;for (int j = 0; j < nums.size() - 1 - i; j++){if (nums[j] > nums[j + 1]){swap(nums[j], nums[j + 1]);isSwap = true;}}if (isSwap == false){break;}}
}void bubbleSortDown(vector<int> &nums)
{for (int i = 0; i < nums.size() - 1; i++){bool isSwap = false;for (int j = 0; j < nums.size() - 1 - i; j++){if (nums[j] < nums[j + 1]){swap(nums[j], nums[j + 1]);isSwap = true;}}if (isSwap == false){break;}}
}

插入排序

void insertSort(vector<int> &nums)
{for (int i = 1; i < nums.size(); i++){int j = i - 1;int temp = nums[i];while (j >= 0 && nums[j] > temp){nums[j + 1] = nums[j];j--;}nums[j + 1] = temp;}
}

选择排序

void selectSort(vector<int> &nums)
{for (int i = 0; i < nums.size() - 1; i++){int minIndex = i;for (int j = i + 1; j < nums.size(); j++){minIndex = nums[minIndex] > nums[j] ? j : minIndex;}if (minIndex != i){swap(nums[i], nums[minIndex]);}}
}

希尔排序

void shellSort(vector<int> &nums)
{for (int step = nums.size() / 2; step > 0; step /= 2){for (int i = step; i < nums.size(); i++){int j = i - step;int temp = nums[i];while (j >= 0 && nums[j] > temp){nums[j + step] = nums[j];j -= step;}nums[j + step] = temp;}}
}

堆排序

void maxHeapify(vector<int> &nums, int pos, int len)
{int child = 2 * pos + 1;while (child < len){if (child + 1 < len && nums[child] < nums[child + 1]){child = child + 1;}if (nums[pos] > nums[child]){return;}else{swap(nums[pos], nums[child]);pos = child;child = 2 * pos + 1;}}
}void minHeapify(vector<int> &nums, int pos, int len)
{int child = 2 * pos + 1;while (child < len){if (child + 1 < len && nums[child] > nums[child + 1]){child = child + 1;}if (nums[pos] < nums[child]){return;}else{swap(nums[pos], nums[child]);pos = child;child = 2 * pos + 1;}}
}void heapSort(vector<int> &nums)
{for (int len = nums.size(); len > 0; len--){for (int i = len / 2 - 1; i >= 0; i--){maxHeapify(nums, i, len);// minHeapify(nums, i, len);}swap(nums[0], nums[len - 1]);}
}

快速排序

void quickSort(vector<int> &nums, int begin, int end)
{if (begin >= end){return;}int left = begin;int right = end;int key = left;while (left < right){while (left < right && nums[right] >= nums[key]){right--;}while (left < right && nums[left] <= nums[key]){left++;}swap(nums[left], nums[right]);}swap(nums[key], nums[left]);key = left;quickSort(nums, begin, key - 1);quickSort(nums, key + 1, end);
}

归并排序

void merge(vector<int> &nums, int begin, int mid, int end)
{vector<int> merArray;int p1 = begin;int p2 = mid;while (p1 < mid && p2 <= end){if (nums[p1] < nums[p2]){merArray.push_back(nums[p1++]);}else{merArray.push_back(nums[p2++]);}}while (p1 < mid){merArray.push_back(nums[p1++]);}while (p2 <= end){merArray.push_back(nums[p2++]);}int index = begin;for (auto it : merArray){nums[index++] = it;}
}void mergeSortIteration(vector<int> &nums)
{for (int i = 0; i < nums.size(); i++){int start = 0;int len = 1 << i;if (len > nums.size()){break;}while (start < nums.size()){int mid = start + len - 1;if (mid > nums.size() - 1){break;}int end = min(start + 2 * len - 1, (int)nums.size() - 1);merge(nums, start, mid + 1, end);start += 2 * len;}}
}void mergeSortRecursion(vector<int> &nums, int begin, int end)
{if (begin < end){int mid = (begin + end) / 2;mergeSortRecursion(nums, begin, mid);mergeSortRecursion(nums, mid + 1, end);merge(nums, begin, mid + 1, end);}
}

桶排序

void bucketSort(vector<int> &nums)
{int maxValue = *max_element(nums.begin(), nums.end());int minValue = *min_element(nums.begin(), nums.end());int range = maxValue - minValue;int count = range / 10 + 1;vector<vector<int>> buckets(count);for (auto it : nums){int index = (it - minValue) / 10;buckets[index].push_back(it);}for (int i = 0; i < count; i++){sort(buckets[i].begin(), buckets[i].end());}int temp = 0;for (auto bucket : buckets){for (auto it : bucket){nums[temp++] = it;}}
}

计数排序

void countSort(vector<int> &nums)
{int maxValue = *max_element(nums.begin(), nums.end());int minValue = *min_element(nums.begin(), nums.end());int range = maxValue - minValue + 1;vector<int> count(range);for (auto it : nums){count[it - minValue]++;}int temp = 0;for (int i = 0; i < range; i++){while (count[i]-- > 0){nums[temp++] = i + minValue;}}
}

基数排序

void cardinalSort(vector<int> &nums)
{vector<vector<int>> buckets(19);int maxValue = *max_element(nums.begin(), nums.end());int minValue = *min_element(nums.begin(), nums.end());int temp = log10(max(abs(minValue), abs(maxValue)));for (int i = 0; i <= temp; i++){for (auto it : nums){int index = abs(it) / (int)pow(10, i) % 10;if (it < 0){index = 9 - index;}else{index = 9 + index;}buckets[index].push_back(it);}int index = 0;for (auto &bucket : buckets){for (auto it : bucket){nums[index++] = it;}bucket.clear();}}
}

算法复杂度及稳定性表格