allsort.cpp~

#include "bits/stdc++.h"
using namespace std;

void bubble_sort(vector<int> &nums)
{
    for (int i = 0; i < nums.size(); i++) { // times
        for (int j = 0; j < nums.size() - i - 1; j++) { // position
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

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

void selection_sort(vector<int> &nums)
{
    for (int i = 0; i < nums.size(); i++) { // position
        int min = i;
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }

        int temp = nums[i];
        nums[i] = nums[min];
        nums[min] = temp;
    }
}

void merge_array(vector<int> &nums, int b, int m, int e, vector<int> &temp)
{
    int lb = b, rb = m, tb = b;
    while (lb != m && rb != e)
        if (nums[lb] < nums[rb])
            temp[tb++] = nums[lb++];
        else
            temp[tb++] = nums[rb++];

    while (lb < m)
        temp[tb++] = nums[lb++];
    
    while (rb < e)
        temp[tb++] = nums[rb++];

    for (int i = b;i < e; i++)
        nums[i] = temp[i];
}

void merge_sort(vector<int> &nums, int b, int e, vector<int> &temp)
{
    int m = (b + e) / 2;
    if (m != b) {
        merge_sort(nums, b, m, temp);
        merge_sort(nums, m, e, temp);
        merge_array(nums, b, m, e, temp);
    }
}

void quick_sort(vector<int> &nums, int b, int e)
{
    if (b < e - 1) {
        int lb = b, rb = e - 1;
        while (lb < rb) {
            while (nums[rb] >= nums[b] && lb < rb)
                rb--;
            while (nums[lb] <= nums[b] && lb < rb)
                lb++;
            swap(nums[lb], nums[rb]);
        }
        swap(nums[b], nums[lb]);
        quick_sort(nums, b, lb);
        quick_sort(nums, lb + 1, e);
    }
}

#define N 10000
#define T 10



int main(){
	srand((unsigned)time(NULL));//随机数
	clock_t start,end;
	vector<int> num;
	vector<int> temp;
	vector<int> change;

	for(int i=0;i<N;i++){
		num.push_back(rand()%1000);
		temp.push_back(num[i]);
		change.push_back(num[i]);
//		cout << num[i] << ' ';
	}
//	cout << endl;
	
	int t1=0,t2=0,t3=0,t4=0,t5=0,t6=0,t7=0;
	
	for(int i=0;i<T;i++){
	
		for(int i=0;i<N;i++) temp[i]=num[i];
		start=clock();
		bubble_sort(temp);
//		for(int i=0;i<N;i++){
//			cout << temp[i] << ' ';
//		}cout << endl;
		end=clock();
		t1+=end-start;
		
		for(int i=0;i<N;i++) temp[i]=num[i];
		start=clock();
		insert_sort(temp);
		end=clock();
		t2+=end-start;
		
		for(int i=0;i<N;i++) temp[i]=num[i];
		start=clock();
		selection_sort(temp);
//		for(int i=0;i<N;i++){
//			cout << temp[i] << ' ';
//		}cout << endl;
		end=clock();
		t3+=end-start;
		
		
		for(int i=0;i<N;i++) temp[i]=num[i];
		start=clock();
		merge_sort(temp,0,N-1,change);
//		for(int i=0;i<N;i++){
//			cout << temp[i] << ' ';
//		}cout << endl;
		end=clock();
		t5+=end-start;
		
		for(int i=0;i<N;i++) temp[i]=num[i];
		start=clock();
		quick_sort(temp,0,N);
//		for(int i=0;i<N;i++){
//			cout << temp[i] << ' ';
//		}cout << endl;
		end=clock();
		t6+=end-start;
	}
	
	cout << "快速排序: " << t6*1.0/T << endl;
    cout << "归并排序: " << t5*1.0/T << endl ;
    cout << "选择排序: " << t3*1.0/T << endl;
    cout << "插入排序: " << t2*1.0/T << endl;
    cout << "冒泡排序: " << t1*1.0/T << endl;
//    cout << "堆排序: " << t7*1.0/T;
}