内部排序(8种)算法实现

C/C++代码实现8种内部排序

#include<iostream> using namespace std; int n;//元素个数 const int maxn = 100;//最大元素个数 int R[maxn / 2 + 2];//右子表 int L[maxn / 2 + 2];//左子表 const int inf = 0x7ffff; void InsertSort(int r[]) { //gap = 1的shell sort for (int i = 2; i <= n; i++) { if (r[i] < r[i - 1]) { r[0] = r[i]; r[i] = r[i - 1];//向后移动 int j = i - 2; while (r[0] < r[j]) //若是r[0]比r[j]小 { r[j + 1] = r[j];//r[j]向后移动 --j;//向前找比r[0]大的记录 }//r[0] >= r[j] r[j + 1] = r[0]; } } } void BiInsertSort(int r[]) { for (int i = 2; i <= n; i++) { r[0] = r[i]; int low = 1; int high = i - 1; while (low <= high) { //int mid = (high + low) / 2; //防止溢出 int mid = high - (high - low) / 2; if (r[0] < r[mid]) high = mid - 1; else low = mid + 1; } int j = i - 1; while (j >= high + 1) { r[j + 1] = r[j]; --j; }//j < hight + 1 j == high r[j + 1] = r[0]; } } void ShellInsert(int r[], int gap) { for (int i = gap + 1; i <= n; i++) { if (r[i] < r[i - gap]) { r[0] = r[i]; int j = i - gap; while (j > 0 && r[0] < r[j]) { //向后移动元素 r[j + gap] = r[j]; j -= gap; } r[j + gap] = r[0]; } } } /* 希尔排序 delta数组是间隔数组 每个元素代表间隔gap大小 t表示delta数组的元素个数 */ void ShellSort(int r[], int delta[], int t) { for (int i = 0; i < t; i++) { ShellInsert(r, delta[i]);//对每一组子序列进行插入排序 } } /*冒泡排序*/ void BubbleSort(int r[]) { for (int i = 1; i < n; i++) //n - 1趟 { for (int j = 1; j <= n - i; j++) //每趟排序会将一个最大值浮到最后面 { if (r[j + 1] < r[j])//交换 将大数放在后面 { int t = r[j + 1]; r[j + 1] = r[j]; r[j] = t; } } } } void Swap1(int* p, int* q) { //下面这种方法可以实现实参值的交换 因为传递的是实参a b的地址 //p指向a q指向b *p = a的值 可以通过修改*p来修改指向内存地址单元的值 //p是int *类型(此函数中形参) *p 是int类型 int temp; temp = *p; *p = *q; *q = temp; //下面这种方法并不能交换实参值 函数传递的是实参a b地址 //因为它只是交换了p q的的值 p指向b的地址 q指向a的地址 并没有改变实参的值 // int *t = p; // p = q; // q = t; } void Swap2(int& p, int& q) {//引用 传递的是地址 int temp = p; p = q; q = temp; } /*排列高低子表元素 最后确定枢轴位置*/ int Partition(int r[], int low, int high) { int pivotkey = r[low];//枢轴记录为r[low] while (low < high) { while (low < high && r[high] >= pivotkey) { high--; }//r[high] < pivotkey //交换high和low指向的记录 Swap1(&r[high], &r[low]); //Swap2(r[high], r[low]); while (low < high && r[low] <= pivotkey) { low++; }//r[low] > pivotkey //交换low和high指向的记录 Swap1(&r[low], &r[high]); } return low; } /*快速排序*/ void QuickSort(int r[], int low, int high) { if (low < high) { int pivotloc = Partition(r, low, high); QuickSort(r, low, pivotloc - 1); //对低子表进行递归排序 QuickSort(r, pivotloc + 1, high);//对高子表进行递归排序 } } /*第二种快排方法*/ int QuickSort_(int r[], int low, int high) { if(low < high) { int pivotkey = r[low];//枢轴记录为r[low] int pl = low; int ph = high; while (low < high) { while (low < high && r[high] >= pivotkey) { high--; }//r[high] < pivotkey if(low < high) r[low++] = r[high]; while (low < high && r[low] <= pivotkey) { low++; }//r[low] > pivotkey if(low < high) r[high--] = r[low]; }//完成一次快排 int pivotloc = low;//确定枢轴位置为low //重要!!!!!! r[pivotloc] = pivotkey; //一次快排结束之后 以low为分界线 r[low]处为上次快排的枢轴记录 QuickSort_(r, pl, pivotloc - 1);//对低字表进行递归排序 QuickSort_(r, pivotloc + 1, ph);//对高子表进行递归排序 } } //选择排序 void SelectSort(int r[]) { for(int i = 1; i < n; i++)// n-1趟 { int k = i; for(int j = i + 1; j <= n; j++)//选择出剩余元素中的最小值 { if(r[j] < r[k]) k = j; } if(k != i)//将第i个元素和剩余元素中的最小值交换 { Swap1(&r[k], &r[i]); //int t = r[i]; //r[i] = r[k]; //r[k] = t; } } } /*合并子表*/ void Merge(int r[], int left, int mid, int right) { //9个元素 left = 1; right = 9+1; mid = (1+9+1)/2 = 5; 10个元素 left = 1; right = 10; mid = 5; int n1 = mid - left;//5 - 1 = 4 for(int i = 0; i < n1; i++) { L[i] = r[left + i]; //1 2 3 4 ... } int n2 = right - mid; //9+1 - 5 = 5 for(int j = 0; j < n2; j++) { R[j] = r[mid + j]; } L[n1] = inf; R[n2] = inf;//末尾元素初始化为无穷大 int i = 0;//L[]元素指针 int j = 0;//R[]元素指针 for(int k = left; k < right; k++) { if(L[i] <= R[j]) r[k] = L[i++]; else r[k] = R[j++]; } } /*归并排序*/ void MergeSort(int r[], int left, int right) { if(left < right - 1)//right = n + 1 ; left = 1; { //下标是1开始所以需要right = n + 1,这样分成左右子表时的元素下标才正确 int mid = (left + right) / 2; MergeSort(r, left, mid);//对左子表进行递归合并排序 MergeSort(r, mid, right);//对右子表进行递归合并排序 Merge(r, left, mid, right);//合并 左右子表 } } /* 调整为大顶堆 子节点下标需要注意： 1. 若是待排序序列下标是1开始的 则父节点的下标是<序列长度/2 = j>, 左孩子结点的下标是<2*j>, 右孩子结点的下标是<2*j+1> 2. 若是待排序序列下标是1开始的 则父节点的下标是<序列长度/2-1 = j>, 左孩子结点的下标是<2*j+1>, 右孩子结点的下标是<2*j+2> */ void HeapAdjust(int r[], int parent, int n) { // 调整r[parent ... n]为大顶堆 parent是父节点 // n下标最大的子节点 也就是待排序序列的长度 // 其实调整的值为 以parent为根节点的二叉树 满足大/小顶堆的定义 int temp = r[parent];//父节点的值暂存 for(int j = 2 * parent; j <= n; j++) { //右孩子是最大的结点 否则 左孩子是最大的节点 if(j < n && r[j] < r[j + 1]) ++j; //父节点值>=右孩子结点值 if(temp >= r[j]) break; //父节点值小于左/右孩子结点值 r[parent] = r[j];//父节点值替换为左/右孩子结点值 parent = j;//parent暂存子节点下标 } //若break，父节点值无需右孩子结点交换值 //否则，子节点的值替换为父节点的值 r[parent] = temp; } /*堆排序*/ void HeapSort(int r[]) { //从第一个非叶子结点n/2开始进行初始大顶堆构建 //元素个数为n个 下标从1开始的序列 非叶子节点下标为 n/2 ~ 1 for(int i = n / 2; i > 0; i--) { HeapAdjust(r, i, n); } for(int i = n; i > 1; i--) { //将大顶堆第一个值（最大）与最后一个值交换 //最后一个值变成最大的 第一个值变成堆顶元素 int t = r[1]; r[1] = r[i]; r[i] = t; //此时还需要调整堆 将1~i-1调整为大顶堆 r[1]为整个堆的根节点 调整即可 HeapAdjust(r, 1, i - 1); } } void print(int r[]) { for (int i = 1; i <= n; i++) { cout << r[i] << " "; } cout << endl; } int main() { cin >> n; int r[maxn + 1]; for (int i = 1; i <= n; i++) cin >> r[i]; //插入排序 //InsertSort(r); //折半插入排序 //BiInsertSort(r); //希尔排序 //int delta[3] = {3, 2, 1}; //int t = 3; //ShellSort(r, delta, t); //冒泡排序 //BubbleSort(r); //快速排序 2种不同的实现 //int low = 1; //int high = n; //QuickSort(r, low, high); //QuickSort_(r, low, high); //选择排序 //SelectSort(r); //归并排序 //int left = 1; //int right = n + 1; //MergeSort(r, left, right); //堆排序 HeapSort(r); print(r); return 0; }