排序整合包（仅供参考）

OTON

2023-09-05 22:34:01

发布于：浙江

18阅读

0回复

0点赞

从我刚开始学C++，就对排序有着深刻的印象。因为我总共学了6种排序只会敲两种比较简单的sort和bubblesort排序。其他的几种只知道思路，代码无从下手。我现在来整理一下我学过的6种排序和我拓展的2种排序，一共8种，代码如下：
sort排序

#include<bits/stdc++.h>
using namespace std;
bool up_or_down(int x,int y){
	return x>y;//这里表示降序排列，想要升序把这个函数删掉或者将x>y变成x<y。 
} 
int main(){
	long a[10005],n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n,up_or_down);
	for(int i=0;i<n;i++) cout<<a[i]<<" ";
	return 0;
}

bubbleSort排序

#include<iostream>
using namespace std;
const long long N=1e5+5;
/*
5 3 4 1 2
3 4 1 2 5
3 1 2 4 5
1 2 3 4 5*/
//冒泡排序（改进后的） 
int main(){
	int n,i,j,temp=0,a[N];
	bool tr;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=n;i>1;i--){
		tr=1;
		for(int j=1;j<i;j++){
			if(a[j]>a[j+1]) swap(a[j],a[j+1]);tr=0;
		}
		if(tr) break;
	}for(int i=1;i<=n;i++) cout<<a[i]<<" "; 
	return 0;
}

insertionSort排序

#include<iostream>
using namespace std;
const long long N=1e5+5;
//插入排序，和冒泡排序一样都是稳定排序
/*基本原理：
5 3 4 1 2
5|3 4 1 2
3 5|4 1 2
3 4 5|1 2
2 3 4 5|1
1 2 3 4 5*/ 
int main(){
	int i,j,k,n,a[N],key;
	float temp;
	cin>>n;
	for(i=1;i<=n;i++) cin>>a[i];
	for(i=1;i<=n;i++){
		for(j=i-1;i>=1;j--){
			if(a[j]<=a[i]) break;
		}if(j!=i-1){
			temp=a[i];
			for(k=i-1;k>j;k--) {
				a[k+1]=a[k];
			}
			a[k+1]=temp;
		}
	}
	for(i=1;i<=n;i++) cout<<a[i]<<" ";
	return 0;
}

quickSort排序

#include <iostream>  
#include <vector>  
using namespace std;  
//快速排序，我的噩梦 
void quickSort(vector<int>& arr, int left, int right) {  
    if (left >= right) {  
        return;  
    }  
    int pivot = arr[left];  
    int i = left, j = right;  
    while (i < j) {  
        while (i < j && arr[j] >= pivot) {  
            j--;  
        }  
        arr[i] = arr[j];  
        while (i < j && arr[i] <= pivot) {  
            i++;  
        }  
        arr[j] = arr[i];  
    }  
    arr[i] = pivot;  
    quickSort(arr, left, i - 1);  
    quickSort(arr, i + 1, right);  
}  
  
int main() {  
    int n;
	cin >> n;  
    vector<int> arr(n); 
    for (int i = 0; i < n; i++) {  
        cin >> arr[i];  
    }  
    quickSort(arr, 0, n - 1); 
    for (int i = 0; i < n; i++) {  
        cout << arr[i] << " ";  
    }  
    cout << endl;  
    return 0;  
}

merge排序

#include <iostream>  
#include <vector>  
 //这个时候就开始恶心起来了，归并排序，我愿堪称最难的排序
using namespace std;  
  
void merge(vector<int>& nums, int left, int mid, int right) {  
    int n1 = mid - left + 1;  
    int n2 = right - mid;  
  
    vector<int> leftArr(n1);  
    vector<int> rightArr(n2);  
  
    for (int i = 0; i < n1; i++) {  
        leftArr[i] = nums[left + i];  
    }  
    for (int j = 0; j < n2; j++) {  
        rightArr[j] = nums[mid + 1 + j];  
    }  
  
    int i = 0, j = 0, k = left;  
    while (i < n1 && j < n2) {  
        if (leftArr[i] <= rightArr[j]) {  
            nums[k++] = leftArr[i++];  
        } else {  
            nums[k++] = rightArr[j++];  
        }  
    }  
    while (i < n1) {  
        nums[k++] = leftArr[i++];  
    }  
    while (j < n2) {  
        nums[k++] = rightArr[j++];  
    }  
}  
  
void mergeSort(vector<int>& nums, int left, int right) {  
    if (left >= right) {  
        return;  
    }  
    int mid = (left + right) / 2;  
    mergeSort(nums, left, mid);  
    mergeSort(nums, mid + 1, right);  
    merge(nums, left, mid, right);  
}  
  
int main() {  
    int n;
    cin >> n;  
    vector<int> nums(n); 
    for (int i = 0; i < n; i++) {  
        cin >> nums[i];  
    }
    mergeSort(nums, 0, n - 1);   
    for (int i = 0; i < n; i++) {  
        cout << nums[i] << " ";  
    }  
    cout << endl;  
    return 0;  
}

bucketSort排序我不建议使用

#include <iostream>  
#include <vector>  
#include <algorithm>    
using namespace std;  
// 桶排序 ，对于空间有要求，这里走个场就好，也有可能是因为我写的太多了 
void bucketSort(vector<float>& arr, int n) {  
    // 找到最大值和最小值  
    float maxValue = *max_element(arr.begin(), arr.end());  
    float minValue = *min_element(arr.begin(), arr.end()); 
    // 创建桶并初始化  
    vector<vector<float>> buckets(n);  
    for (int i = 0; i < n; i++) {  
        buckets[i].reserve(1);  
    }
    // 将元素分配到各个桶中  
    for (int i = 0; i < n; i++) {  
        int bucketIndex = (arr[i] - minValue) * (n - 1) / (maxValue - minValue);  
        buckets[bucketIndex].push_back(arr[i]);  
    }  
    // 对每个桶中的元素进行排序  
    for (int i = 0; i < n; i++) {  
        sort(buckets[i].begin(), buckets[i].end());  
    }  
    // 将排序后的元素按顺序放回原数组  
    int index = 0;  
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < buckets[i].size(); j++) {  
            arr[index++] = buckets[i][j];  
        }  
    }  
}  
int main() {  
    int n;  
    cin >> n;  
    vector<float> arr(n); 
    for (int i = 0; i < n; i++) {  
        cin >> arr[i];  
    }  
    bucketSort(arr, n); 
    for (int i = 0; i < n; i++) {  
        cout << arr[i] << " ";  
    }  
    cout << endl;  
    return 0;  
}

接下来是拓展排序，我目前还没学到，如果有学到的大佬帮我改一下（纯粹是看资料的好吗）
heapSort排序（这里面做了一些预习，发现要用到树。啊！）

#include <iostream>  
using namespace std;  
void heapify(int arr[], int n, int i) {  
    int largest = i; // 初始化最大值为根节点  
    int l = 2 * i + 1; // 左子节点  
    int r = 2 * i + 2; // 右子节点  
    // 如果左子节点比根节点大，更新最大值为左子节点  
    if (l < n && arr[l] > arr[largest]) {  
        largest = l;  
    }  
    // 如果右子节点比根节点大，更新最大值为右子节点  
    if (r < n && arr[r] > arr[largest]) {  
        largest = r;  
    }  
    // 如果最大值不是根节点，就交换根节点和最大值，并递归地对交换后的子树进行堆化  
    if (largest != i) {  
        swap(arr[i], arr[largest]);  
        heapify(arr, n, largest);  
    }  
}  
void heapSort(int arr[], int n) {  
    // 构建最大堆，即对数组进行堆化  
    for (int i = n / 2 - 1; i >= 0; i--) {  
        heapify(arr, n, i);  
    }  
    // 从最后一个元素开始，每次将最大值（即根节点）交换到数组末尾并进行堆化，得到新的最大值  
    for (int i = n - 1; i >= 0; i--) {  
        swap(arr[0], arr[i]);  
        heapify(arr, i, 0);  
    }  
}  
int main() {  
    int n; 
    cin >> n;  
    int arr[n];  
    for (int i = 0; i < n; i++) {  
        cin >> arr[i];  
    }
    heapSort(arr, n);  
    for (int i = 0; i < n; i++) {  
        cout << arr[i] << " ";  
    }  
    cout << endl;  
    return 0;  
}

shell排序（个人认为可以记一记）

#include <bits/stdc++.h>   
using namespace std;  
//希尔排序是插入排序的另一种形式，不过不像插入排序那样稳定 
int main() {  
    int n;  
    cin >> n;
    vector<int> arr(n);  
    for (int i = 0; i < n; i++) {  
        cin >> arr[i];  
    } for (int gap = n / 2; gap > 0; gap /= 2) {  
        for (int i = gap; i < n; i++) {  
            int temp = arr[i];  
            int j;  
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {  
                arr[j] = arr[j - gap];  
            }  
            arr[j] = temp;  
        }  
    }  
    for (int i = 0; i < n; i++) {  
        cout << arr[i] << " ";  
    }  
    cout << endl;  
    return 0;  
}