不多说废话了，直接贴上代码，个人把常用的排序算法写成了一个类，方便随时调用，部分内容待后续补充
//main.cpp #include "sort.h" int main() { Sort sort_class; int test_array[10] = { 10,5,5,9,3,55,6,3,1,0 }; sort_class.len = sizeof(test_array) / sizeof(test_array[0]); // sort_class.bubbleSort(test_array); //sort_class.half_insertSort(test_array); sort_class.shellSort(test_array); sort_class.print(test_array); return 0; } #pragma once //sort.h #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <math.h> using namespace std; #define ElemType int class Sort { public: int len; // 交换排序 void bubbleSort(ElemType *array); int partition(ElemType *array, int low, int high); //划分函数是快排的关键 void quickSort(ElemType *array, int low, int high); // 实际执行的是这个 void quickSort(ElemType *array); //调用这个即可，为了统一各个排序函数的调用方式 // 选择排序 void selectSort(ElemType *array); void heapSort(ElemType *array); // 插入排序 void insertSort(ElemType *array); void half_insertSort(ElemType *array); //折半插排 void shellSort(ElemType *array); void swap(ElemType *array, int i, int j); void print(ElemType *array); }; //sort.cpp #include "sort.h" void Sort::swap(ElemType *array, int i, int j) { auto temp = array[i]; array[i] = array[j]; array[j] = temp; } void Sort::bubbleSort(ElemType *array) { printf("bubbleSort:\n"); for (int i = 0; i < len; i++) { bool flag = false; for (int j = i + 1; j < len; j++) { if (array[i] > array[j]) { swap(array, i, j); flag = true; // 如果本轮遍历发生交换，则则设置flag } } if (flag == false) { return; //说明剩下的都是有序了，相比无flag比较次数少点 } } } int Sort::partition(ElemType *array, int low, int high) { auto pivot = array[low]; // 将当前表中第一个元素作为枢轴元素，占用O（1）的空间 这时候low已经备份，可以覆盖 while (low < high) { while (low < high && array[high] >= pivot) --high; //比枢轴大的元素放在右边不动 array[low] = array[high]; // 碰到比枢轴小的，移到左边 这时候high已经备份，可以覆盖 while (low < high && array[low] >= pivot) ++low; //比枢轴小的元素放在左边不动 array[high] = array[low]; // 碰到比枢轴大的，移到右边 这时候新的low已经备份，可以覆盖 } array[low] = pivot; // 枢轴元素存放到最终的位置 将第一个备份的放回去 return low; //返回枢轴元素的位置 } void Sort::quickSort(ElemType *array, int low, int high) { int pivotPos = 0; while (low < high) { pivotPos = partition(array, low, high); quickSort(array, low, pivotPos); // 对左边部分递归快排 quickSort(array, pivotPos, high); //对又变部分递归快排 } } void Sort::quickSort(ElemType *array) { /* 快排是对冒泡排序的一种改进。 基本思想：基于分治法 */ printf("quickSort:\n"); int low = 0, high = len - 1; quickSort(array, low, high); } void Sort::selectSort(ElemType *array) { /* 简单选择排序 基本思想：每一趟（如第i趟）在后面n-i+1（i=1,2...,n-1）个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素。 选择排序的时间复杂度为：O(n^2)，空间复杂度：O(1) 选择排序是不稳定的； */ printf("selectSort:\n"); int min_pos; //记录最小元素的位置 for (int now_start = 0; now_start < len - 1; now_start++) { min_pos = now_start; for (int j = now_start+1; j < len; j++) { if (array[j] < array[min_pos]) min_pos = j; //更新最小元素的位置 } if (min_pos != now_start) swap(array, now_start, min_pos); // 将第i小的元素与第i个位置的元素互换 } } void Sort::heapSort(ElemType *array) { /* 堆排序是一种树形选择排序方法 */ printf("heapSort:\n"); } void Sort::insertSort(ElemType *array) { /* 直接插入排序 基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中 感觉像是逐步遍历逆序数 适用于基本有序的排序表和数据量不大的排序表 */ printf("insertSort:\n"); int i, j; int temp; for (i = 1; i < len; i++) { if (array[i] < array[i - 1]) { temp = array[i]; //哨兵，好多情况下把array[0]作为哨兵，不存放元素，数组总长度为n+1，我这里单独搞了一个temp，考虑到这是一个类，尽量和其他的排序方法参数兼容 for (j = i - 1; temp < array[j]; j--) array[j + 1] = array[j]; //元素后移 array[j + 1] = temp; // 发现第j个位置的元素已经小于temp,所以把temp放到第j+1个位置 } } } void Sort::half_insertSort(ElemType *array) { /* 折半插入排序 基本思想：与直接插排的区别在于，直接插排是边比较变移动，需要移动多少个就需要比较多少次 而折半插排是将比较和移动这两个操作进行了分离，先确定插入位置，再移动元素， 好处在于：折半查找的方式减少了比较的次数 注：移动操作的次数无论如何是不能被减少的（除非你用链表，就不需要移动了，但是用了链表之后折半查找方式就行不通了） */ printf("half_insertSort:\n"); int i, j; int temp; int low, high, mid; for (i = 1; i < len; i++) { if (array[i] < array[i - 1]) { temp = array[i]; //哨兵，好多情况下把array[0]作为哨兵，不存放元素，数组总长度为n+1，我这里单独搞了一个temp，考虑到这是一个类，尽量和其他的排序方法参数兼容 low = 0; high = i - 1; // while (low <= high) { mid = (low + high) / 2; if (array[mid] < temp) low = mid + 1; else high = mid - 1; } for (j = i - 1; j > high; j--) array[j + 1] = array[j]; //元素后移 array[high + 1] = temp; // 发现第j个位置的元素已经小于temp,所以把temp放到第j+1个位置 } } } void Sort::shellSort(ElemType *array) { /* 希尔排序（有称缩小增量排序） 基本思想：弥补直接插排的缺陷（只适用于基本有序的和数据量不大的）， 步长的理解：并不是按照多少步长进行划分一组，比如dk,dk+1,...,2dk-1是一组 而是dk,2dk,3dk...这些是一组。注意区别归并排序 */ printf("shellSort:\n"); int dk; int temp; int i, j; for (dk = len / 2; dk >= 1; dk /= 2) { for (i = dk + 1; i < len; i++) { //在每一个组里面采用的仍旧是插入排序 if (array[i] < array[i - dk]) { temp = array[i]; for (j = i - dk; j >= 0 && temp < array[j]; j -= dk) array[j + dk] = array[j]; array[j + dk] = temp; } } } } void Sort::print(ElemType *array) { for (int i = 0; i < len; i++) printf("%d ", array[i]); }
