【C++】【十二】排序实现及思路

掌握核心知识点：

1.插入排序在一下2种情况效率较高：1）数据基本有序  2）数据序列较少

希尔排序是在插入排序的基础上的改进。

2.快速排序

3.归并排序

4.堆排序：数据初始化为数据，根据完全二叉树，初始化并且调整堆的顺序

//冒泡排序
#include <iostream>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>
#include<sys/timeb.h>#define MAX 10long GetSysTime() {struct timeb tb;ftime(&tb);return tb.time * 1000 + tb.millitm;
}void Swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}void PrintArray(int arr[],int length) {for (int i = 0; i < length; ++i) {printf("%d ", arr[i]);}printf("\n");
}
//原始冒泡排序
void BubbleSort(int arr[], int length) {for (int i = 0; i < length; ++i) {for (int j = length-1; j > i; j--) {if (arr[j-1] < arr[j]) {//降序Swap(&arr[j-1],&arr[j]);}}}
}void BubbleSortImprovement(int arr[], int length) {int flag = 0;//表示 未排序for (int i = 0; i < length&&flag==0; ++i) {flag = 1;//认为未排序好for (int j = length - 1; j > i; j--) {if (arr[j - 1] < arr[j]) {//降序flag = 0;Swap(&arr[j - 1], &arr[j]);}}}
}
//选择排序
void SeleteSort(int arr[], int length) {for (int i = 0; i < length; ++i) {int min = i;for (int j = i+1; j < length; ++j) {if (arr[j] < arr[min]) {min = j;}}if (min != i) {Swap(&arr[i], &arr[min]);}}
}
//插入排序  1.将无序序列，插入到有序序列中   什么情况下，效果高：
//1）序列基本有序的情况下，插入效率高；
//2）插入排序时，元素序列比较少的情况下
void InsertSort(int arr[], int length) {int i, j, temp;for (i = 1; i < length;++i) {//升序if (arr[i] < arr[i - 1]) {temp = arr[i];for (j = i - 1; j >= 0 && temp < arr[j]; --j) {arr[j + 1] = arr[j];}arr[j + 1] = temp;}}
}
//分组插入排序
//对每一组分别进行插入排序
//increment=length increment=increment/3+1
void ShellSort(int arr[], int length) {//从小到大  rename 减少增量排序int increasement = length;do {int i, j, k;increasement = increasement / 3 + 1;for ( i = 0; i < increasement; ++i) {            for (j = i + increasement; j < length; j+=increasement) {if (arr[j] < arr[j - increasement]) {int temp = arr[j];for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement) {arr[k + increasement] = arr[k];}arr[k + increasement] = temp;}}}} while (increasement > 1);
}
//分治法（大问题分成小问题，解决小问题，从而解决大问题）+ 挖坑填数
void QuickSort(int arr[],int start,int end) {//从小到大int i = start;int j = end;int temp = arr[start];//基准数if (i < j) {while (i<j){//从右向左找比基准数小while (i < j && arr[j] >= temp) {j--;}if (i < j) { //填坑arr[i] = arr[j];i++;}//从左向右找比基准数大的数while (i < j && arr[i] < temp) {i++;} if (i < j) { //填坑arr[j] = arr[i];j--;}}//把基准数放到 i，j位置arr[i] = temp;//对基准数左半部分快速排序QuickSort(arr, start, i - 1);//右半部分QuickSort(arr, i + 1, end);}
}//归并排序：思想：将2个有序序列合并成一个有序序列int* CreatArray() {int* arr = (int*)malloc(sizeof(int)*MAX);srand((unsigned int)time(NULL));for (int i = 0; i < MAX; ++i) {arr[i] = rand() % MAX;}return arr;
}void Merge(int arr[],int start,int end,int mid,int* temp) {int i_start = start;int i_end = mid;int j_start = mid + 1;int j_end = end;int length = 0;//辅助空间元素//合并两个有序序列while (i_start <= i_end && j_start <= j_end){if (arr[i_start] < arr[j_start]) {temp[length] = arr[i_start];length++;i_start++;}else {temp[length] = arr[j_start];j_start++;length++;}} //i 序列while (i_start <= i_end) {temp[length] = arr[i_start];i_start++;length++;}while (j_start <= j_end) {temp[length] = arr[j_start];j_start++;length++;}//辅助空间数组，覆盖到原空间for (int i = 0; i < length; ++i) {arr[start + i] = temp[i];}
}
void MergeSort(int arr[], int start,int end,int* temp) {//从小到大if (start >= end) {return;}int mid = (start + end) / 2;//分组//左半边MergeSort(arr, start, mid, temp);//右半边MergeSort(arr, mid + 1, end, temp);Merge(arr, start, end, mid, temp);
}//堆排序 任意节点（非叶子节点）：大顶堆从小大
// 给出一个数组 相当于给出一个完全二叉树 啊hi不满足堆的条件，通过调整堆
// 初始化堆，从下往上i=len/2,i--;
//待调整数组，待调整系欸但下表  待调整数组长度void myswap(int arr[], int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;
}
void HeapAdjust(int arr[], int index, int len) {int max = index;int lchild = index * 2 + 1;int rchild = index * 2 + 2;if (lchild<len && arr[lchild]>arr[max]) {max = lchild;}if (rchild<len && arr[rchild]>arr[max]) {max = rchild;}if (max != index) {myswap(arr, max, index);HeapAdjust(arr, max, len);}}void HeapSort(int arr[], int length) {//初始化堆 for (int i = length / 2 - 1; i >= 0; i--) {HeapAdjust(arr, i, length);}//交换堆顶元素for (int i = length - 1; i >= 0; i--) {myswap(arr, 0, i);HeapAdjust(arr, 0, i);}
}int main(void) 
{int arr[MAX];int arr2[MAX];srand((unsigned int)time(NULL));for (int i = 0; i < MAX; ++i) {arr[i] = rand() % MAX;arr2[i]= rand() % MAX;}//PrintArray(arr, MAX);//printf("-------insertt-------\n");//long t_start = GetSysTime();//InsertSort(arr, MAX);//long t_end = GetSysTime();//printf("%d,%d\n", MAX, t_end-t_start);//PrintArray(arr, MAX);//printf("---------shell------\n");//long t_shell_start = GetSysTime();//ShellSort(arr2, MAX);//long t_shell_end = GetSysTime();//printf("%d,%d\n", MAX, t_shell_end - t_shell_start);printf("-------quick--------\n");PrintArray(arr, MAX);//long t_quick_start = GetSysTime();//QuickSort(arr, 0, MAX - 1);//long t_quick_end = GetSysTime();//printf("%d,%d\n", MAX, t_quick_end - t_quick_start);PrintArray(arr, MAX);//printf("----merge----\n");PrintArray(arr, MAX);//long t_merge_start = GetSysTime();//int* temp = (int*)malloc(sizeof(int));//MergeSort(arr2, 0, MAX-1, temp);//long t_merge_end = GetSysTime();//printf("%d,%d\n", MAX, t_merge_end - t_merge_start);PrintArray(arr, MAX);//free(temp);printf("--------heap--------\n");HeapSort(arr, MAX);PrintArray(arr, MAX);printf("-------------------------\n");system("pause");return 0;
}