几种常见的排序算法-c++

冒泡、插入、归并、快排、选择

class SORT {
public:
    SORT() {
        for (int i = 0; i < array_SIZE; i++) {
        cout << "...Please input the num: ";
        cin >> a[i]; 
        }
        int p;
        cout << endl << "选择您要进行的排序: " << endl
        << "...1.选择排序" << endl
        << "...2.快速排序" << endl
        << "...3.冒泡排序" << endl
        << "...4.归并排序" << endl
        << "...5.插入排序" << endl;
        cin >> p;
        cout << "-------------------------------------" << endl;
        switch (p) {
        case 1:  this->Select_Sort(); break;
        case 2:  this->Fast_Sort();   break;
        case 3:  this->MaoPao_sort(); break;
        case 4:  this->Merge_sort_API(); break;
        case 5:  this->Insert_sort(); break;
        default: exit(0);
       }
    }
public:
    void Fast_Sort() {  //快排API
        //快排:
        SORT::fast_sort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
        cout << endl << endl << "快排后: " << endl;
        for (int i = 0; i < array_SIZE; i++) {
             cout << a[i] << ' ';
        }
    }
    void Select_Sort() {  //选排API
        //选择排序:
        SORT::select_sort(a, sizeof(a) / sizeof(a[0]));
        cout << endl << endl << "选择排序后: " << endl;
        for (int i = 0; i < array_SIZE; i++) {
             cout << a[i] << ' ';
        }
    }
    void MaoPao_sort() {  //冒泡API
        SORT::maopao_sort(a, sizeof(a) / sizeof(a[0]));
        cout << endl << endl << "冒泡排序后: " << endl;
        for (int i = 0; i < array_SIZE; i++) {
             cout << a[i] << ' ';
        }
    }
    void Merge_sort_API() {
        Merge_sort(a, 0, array_SIZE - 1);  //归并API
        cout << endl << endl << "归并排序后: " << endl;
        for (int i = 0; i < array_SIZE; i++) {
        cout << a[i] << ' ';
        }
    }  
   void Merge_sort(int a[], int low, int high) {  
        if (low == high) {  //将数组拆分成一个元素一个元素
            return;
        }
        int mid = low + (high - low) / 2; //防止left+right越界
        Merge_sort(a, 0, mid);  //左边排序
        Merge_sort(a, mid + 1, high);   //右边排序
        //两路归并
        SORT::merge(a, low, mid + 1, high);  //整体归并
   }
   void Insert_sort() {  //插入API
      for (int i = 1; i < array_SIZE; i++) { //设第一个元素为有序，后面的为待排序数组
        int temp = a[i];    //待排序数组的第一个元素
        int index = i - 1;  //有序数组的最后一个元素下标/待排序数组的前一个元素下标
        //接下来依次作比较(假设从小到大)
        while (index >= 0 && temp <= a[index]) {
        a[index + 1] = a[index];  //元素后移
        --index;
        }
        a[index + 1] = temp;    //找到合适的空位，放入
      }
        cout << endl << endl << "插入排序后: " << endl;
        for (int i = 0; i < array_SIZE; i++) {
        cout << a[i] << ' ';
      }
   }
private:
    void fast_sort(int nums[], int L, int R){
    	if(L >= R){
        	return;
    	}
    	int i = L;
    	int j = R;
    	int key = nums[i];
    
    	while(i < j){
       	 	while(i < j && nums[j] >= key){
            	--j;
        	}
        	if(i < j){
            	//此时nums[j] < key, 应当放在左边, 也就是i的位置
            	nums[i] = nums[j];
        	}
        	while(i < j && nums[i] <= key){
            	++i;
        	}
        	if(i < j){
            	//此时nums[i] > key, 应当放在右边, 也就是j的位置
            	nums[j] = nums[i];
        	}
        	if(i == j){
            	//如果i, j重合, 中间值确定为key
            	nums[i] = key; 
        	}
    	}
    	fast_sort(nums, L, j - 1); //[L,j-1]左部分快排
    	fast_sort(nums, j + 1, R); //[j+1,R]右部分快排
	}
    void select_sort(int a[], int len) {
        int i, j, max;
        for (i = 0; i < len; i++) {
             max = i;    //默认指定第一个数为最大值，下标赋给max
             for (j = i; j < len; j++) {       //接下来选择出真正的最大值，并将下标赋给max
                 if (a[j] >= a[max]) {
                     max = j;
                 }
             }
             if (i != max) {           //max已经改变了，不再是i，说明后面有数比a[i]大
                          //如此往复，就依次把剩余的最大的数往前放
                 int temp = a[i];
                 a[i] = a[max];
                 a[max] = temp;
             }
        }
    }   
    void maopao_sort(int a[], int len) {
        int i, j;
        for (i = 0; i < len - 1; i++) {
            for (j = 0; j < len - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }            
    void merge(int a[], int left, int right, int bound) {
        // left为待排序部分的左边界，bound为右边界，right为中介(左、右两边都排好的)
        int mid = right;  // left . . . right . . . bound。   right左右两边是排好序的
        int i = left;     //左边界
        int j = right;    //中介. 
        int k = 0;
        int *temp = new int[bound - left + 1];  //待排序数组的大小
        while (i < mid && j <= bound) {
            temp[k++] = (a[i] <= a[j] ? a[i++] : a[j++]);
        }

        while (i == mid && j <= bound) {   //左边先走完
            temp[k++] = a[j++];
        }
        while (j > bound && i < mid) {     //右边先走完
           temp[k++] = a[i++];
        }
        for (int i = 0; i < bound - left + 1; i++) {
           a[left + i] = temp[i];       //将归并后的数组的值赋给原数组 a[left,bound]
                                       //要从[left+i,bound]开始赋值，保证传进来的数组区间都得到赋值
        }
        delete []temp;
    }
    static const int array_SIZE = 10;
    int a[array_SIZE];
};

int main() {
    SORT test;  
    system("pause");
    return 0;
}
     

下面是一个测试案例