#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;
}
评论10