排序算法（直接插入排序、折半排序、直接选择排序、快速排序与归并排序）

#include <ctime> #include <cstdlib> #include <cstring> #include <iostream> using namespace std; typedef int ElemType ; extern int quick_count_sort = 0; extern int quick_count_move = 0; // 直接插入排序 void insertSort(ElemType array[], int n){ cout << endl << "Direct insertion sort (from small to large)" << endl; int count_sort = 0, count_move = 0; int i, j, temp; for(i = 1; i < n; i++){ temp = array[i]; for(j = i - 1; temp < array[j]; j--){ array[j + 1] = array[j]; // 所有符合规定元素后移 count_move ++; count_sort ++; if(j == -1){ break; // 防止越界 } } array[j + 1] = temp; // 插入位置插入当前元素 } cout << "Number of data comparisons: " << count_sort << endl; cout << "Number of data moves: " << count_move << endl; } // 折半排序 void binaryInsertSort(ElemType array[], int n){ cout << endl << "Half sort (from small to large)" << endl; int count_sort = 0, count_move = 0; int front, temp, end; for(int i = 1; i < n; i++){ temp = array[i]; front = 0; end = i - 1; while(front <= end){ int mid; mid = (front + end) / 2; if(temp < array[mid]){ count_sort ++; end = mid - 1; }else{ count_sort ++; front = mid + 1; } } for(int j = i; j > front; j--){ array[j] = array[j - 1]; // 所有元素后移 count_move ++; } array[front] = temp; count_move ++; } cout << "Number of data comparisons: " << count_sort << endl; cout << "Number of data moves: ：" << count_move << endl; } // 声明交换函数 void swap(ElemType array[], int i, int j){ int temp = array[j]; array[j] = array[i]; array[i] = temp; } // 直接选择排序 void selectSort(ElemType array[], int n){ cout << endl << "Straight selection sort (from small to large)" << endl; int count_sort = 0, count_move = 0; // 排序循环 for(int i = 0; i < n - 1; i++){ // 默认下标最小的数开始 int temp_i = i; for(int j = i + 1; j < n; j++){ // 比较大小，并交换下标 count_sort ++; if(array[j] < array[temp_i]){ temp_i = j; } } swap(array, temp_i, i); // 交换数据 count_move ++; } cout << "Number of data comparisons: " << count_sort << endl; cout << "Number of data moves: " << count_move << endl; } // 快速排序 void quickSort(ElemType array[], int left, int right){ if(left >= right) return; int i, j , base; i = left, j = right; base = array[left]; while(i < j){ while(array[j] >= base && i < j) { j--; quick_count_sort ++; } while(array[i] <= base && i < j) { i++; quick_count_sort ++; } if(i < j){ swap(array, i, j); quick_count_move ++; } } array[left] = array[i]; quick_count_move ++; array[i] = base; quick_count_move ++; quickSort(array, left, i-1); quickSort(array, i + 1, right); } void quickSortIn(ElemType array[], int left, int right){ cout << endl << "Quick sort (from small to large)" << endl; quickSort(array, left, right); cout << "Number of data comparisons: " << quick_count_sort << endl; cout << "Number of data moves: " << quick_count_move << endl; } // 随机生成数组 void randMatrix(ElemType array[], int n, int Max){ srand((unsigned int)time(0)); for(int i = 0; i < n; i++){ array[i] = rand() % Max; } } // 合并列表 void mergeList(ElemType array[], int p, int q, int mid){ int i = p, j = mid + 1, k = 0; // 申请空间 int *newarray = (int *)malloc((q - p + 1)*sizeof(int)); if(!newarray){ cout << "MallocError" << endl; } while(i <= mid && j <= q){ if(array[i] < array[j]) newarray[k++] = array[i++]; else newarray[k++] = array[j++]; } while(i <= mid) newarray[k++] = array[i++]; while(j <= q) newarray[k++] = array[j++]; for(i = p, k=0; k<(q - p + 1); i++, k++) array[i] = newarray[k]; free(newarray); // 释放空间 } // 归并排序 void mergeSort(ElemType array[], int p, int q){ if(p >= q) return; int mid = (int)((p + q) / 2); // 取中值 // 递归 mergeSort(array, p, mid); mergeSort(array, mid+1, q); // 合并列表 mergeList(array, p, q, mid); } void getRevrse(ElemType array[], int n){ int count = 0; int temp; for(int i = 1; i < n; i++){ temp = array[i]; for(int j = 0; j < i; j++){ if(array[j] > temp) count++; } } cout << "The number of inversions is: " << count << endl; } void getIndex(ElemType *array, ElemType *array_count){ ElemType temp_array[2 * N]= {0}; int index = 0, j = 0, end = 0; int max_count = array_count[0]; for(int i = 0; i < 2 * N; i ++){ if(array_count[i] == 0) break; if(array_count[i] >= max_count) max_count = array_count[i]; } for(int i = 0; i < 2 * N; i++){ if(array_count[i] == 0) { end = i; break; } if(array_count[i] == max_count) { for (int k = 0; k <= i; k++) index += array_count[k]; temp_array[j++] = index - 1; index = 0; } } cout << "The most frequent element: "; for(int i = 0; i < 2 * N; i++){ if(temp_array[i] == 0) { break; } cout << array[temp_array[i]] << " "; } cout << endl << "The first three elements: "; for(int i = end; i > end - 3; i--){ index = 0; for(j = 0; j < i; j++) index += array_count[j]; cout << array[index-1] << " "; } } // 获取出现频次最多的元素与前三大元素，可能存在多个相同频次的元素 void elementCount(ElemType *array){ ElemType temp = array[0]; ElemType array_count[2 * N] = {0}; for(int i = 0, j = 0; i < 2 * N; i ++){ if(array[i] == temp) array_count[j]++; else{ array_count[++j]++; temp = array[i]; } } getIndex(array, array_count); } void getOrder(ElemType array[], int n){ int count_0 = 0; int temp; for(int i = 1; i < n; i++){ temp = array[i]; for (int j = 0; j < i; j++){ if(array[j] <= temp) count_0 ++; } } cout << "The number of order degree is: " << count_0 << endl; } void printMatrix(ElemType array[], int n){ for(int i = 0; i < n; i++){ cout << array[i] << " "; } cout << endl; } int main(){ // ElemType array[5] = {8,4,3,2,0}; int n = 10; int Max = 100; int array[n]; randMatrix(array, n, Max); int tem_array[n]; memcpy(tem_array, array, sizeof(tem_array)); // 复制数据 insertSort(tem_array, n); // binaryInsertSort(tem_array, n); // selectSort(tem_array, n); // quickSort(tem_array, 0, n-1); // mergeSort(tem_array, 0, n); elementCount(tem_array); printMatrix(tem_array, n); return 0; }