九种经典排序算法汇总

/*********************************************************** 总结各种排序算法包括但不限于： 1. 插入排序类 1.1 直接插入排序 1.2 2分插入排序 1.3 希尔排序 2. 交换排序类 2.1 冒泡排序 2.2 快速排序 3. 选择排序 3.1 直接选择排序 3.2 堆排序 4. 归并排序 5. 基数排序 以上所有排序算法的实现均为将整形数组data递增排序 ************************************************************/ #include#include using namespace std; /********************** 1 直接插入排序******************************** 空间复杂度：只有辅助变量， 没有与问题范围相干的辅存消耗，O(1) 时间复杂度：最好情况，初始数组为正序（此处为递增），O(n)；最坏情况，初始数组为反 序，O(n2)；平均时间复杂度为O(n2). 稳定性：当data[i]=datda[i⑴]时，相对位置不变，所以是稳定的排序 思想：将原序列分为有序区和无序区，每次外部循环将无序区的第1个元素插入到有序区的适 当位置，同时有序区元素加1，无序区元素减1，这样直到无序区的元素为0 *******************************************************************/ void insertSort(int data[], int n) { int i, j; int tmp; for (i = 1; i < n; ++i) { tmp = data[i]; j = i - 1; while (j >= 0 && tmp < data[j]) { data[j + 1] = data[j]; --j; } //若j<0则tmp是有序区的最小元素，若tmp>=data[j]则将tmp放在data[j]的 //后面data[j+1]处 data[j + 1] = tmp; } } /************************ 2 2分（折半）插入排序 *********************** 时空复杂度及稳定性与上面是1样的 思想：对有序的序列2分查找效力比顺序查找高很多，基于此，在将无序区的第1个元素插 入到有序区相应位置时，用2分查找寻觅该位置而不是顺序查找，可以减少关 键字比较的次数但是关键字移动的次数依然是没有改变的，所以其实际的效果与直接插 入排序相当，只需注意2分查找思想的应用。 *******************************************************************/ void biInsertSort(int data[], int n) { int i, j, low, high, mid; int tmp; for (i = 1; i < n; ++i) { tmp = data[i]; low = 0, high = i - 1; while (low <= high) { mid = (low + high) / 2; if (tmp < data[mid]) high = mid - 1; else low = mid + 1; } for (j = i - 1; j >= high + 1; --j)//high+1 is mid data[j + 1] = data[j]; data[high + 1] = tmp; } } /************************* 3 希尔排序 ******************************** 空间复杂度：只用到了i,j,gap,tmp4个辅助变量，与问题范围无关，空间复杂度为O(1). 时间复杂度：分析较复杂，1般认为平均时间复杂度为O(n^1.3). 稳定性：不稳定 思想：本质上还是属于插入排序，只不过是先对序列分组，然后组内直接插入，同时，分组数 由多到少，组内元素由少到多，顺序性由差到好，直到最后1步组间距为1时， 直接插入排序的数组已基本有序了 *******************************************************************/ void shellSort(int data[], int n) { int i, j, gap; int tmp; gap = n / 2; while (gap > 0) { //这样记忆，全部for循环其实就是直接插入排序的进程，只不过将直接插入排序 //的1->gap罢了，最后当gap=1的时候就是直接插入排序了。 for (i = gap; i < n; ++i) { tmp = data[i]; j = i - gap; while (j >= 0 && tmp < data[j]) { data[j + gap] = data[j]; j = j - gap; } data[j + gap] = tmp; } gap = gap / 2; } } /*************************** 4 冒泡排序 ****************************** 空间复杂度：只有3个辅助变量，与问题范围无关，空间复杂度为O(1) 时间复杂度：最好情况，数组本身是正序的，O(n)；最坏情况，数组是反序的，O(n^2)；平 均时间复杂度为O(n^2)。 稳定性：稳定 思想：将数组头部看成水面，数组尾部看成水底，最小（或最大）的元素上浮（或下沉）直到 结束，采取的是比较元素大小然后交换元素值的思想，每次都选择未排序的 元素中最小或最大元素投递指定的位置。 *******************************************************************/ //经典冒泡排序算法，以后以这个为准 void bubbleSort(int data[], int n) { int i, j, tmp, flag; for (i = 0; i < n - 1; ++i) { flag = 0; for (j = 0; j < n - i - 1; ++j) { if (data[j] > data[j + 1]) { tmp = data[j]; data[j] = data[j + 1]; data[j + 1] = tmp; flag = 1; } } if (flag == 0) return; } } //最小元素上浮 void bubbleSort1(int data[], int n) { int tmp, flag; for (int i = 0; i < n - 1; ++i) { flag = 0; for (int j = n - 1; j > i; --j) { if (data[j] < data[j - 1]) { tmp = data[j]; data[j] = data[j - 1]; data[j - 1] = tmp; flag = 1; } } if (flag == 0)//no swap in the circulation return; } } //最大元素下沉（备选方案，与上面是1样的） void bubbleSort2(int data[], int n) { int tmp, flag; for (int i = n⑴; i > 0; --i) { flag = 0; for (int j = 0; j < i; ++j) { if (data[j] > data[j + 1]) { tmp = data[j]; data[j] = data[j + 1]; data[j + 1] = tmp; flag = 1; } } if (flag == 0) return; } } /***************************** 5 快速排序 **************************** 空间复杂度：主要是递归时所需的栈空间，平均空间复杂度为O(nlongn)。 时间复杂度：主要的时间都花费在划分上面，最好情况，每次划分的基准都是无序区的‘中 值’记录，O(nlogn);最坏情况，原数组本身是有序的，此时O(n^2)。 平均时间复杂度为O(nlogn)。 稳定性： 不稳定 思想：分治的思想，将大问题转化为小问题，递归的思想，最重要的进程就是划分，划分结束 了，数组也就排好序了，快速排序是排序算法中非常重要的1种 *******************************************************************/ //快排，数据结构书上的方法,递归，以后以这个为准 void quickSort(int data[], int start, int end) { int i = start, j = end; int pivot; if (start < end) { //每次递归都取无序区的第1个元素作为中心基准，这个地方可以改进为随机的方法 pivot = data[start]; while (i != j) { while (j>i && data[j] > pivot) --j; data[i] = data[j]; while (i < j && data[i] < pivot) ++i; data[j] = data[i]; } data[i] = pivot; quickSort(data, start, i - 1); quickSort(data, i + 1, end); } } //另外1个版本是将划分（上面if里面的代码）进程单独成为1个partition函数,同时采样随机化快排思想(剑指offer) int randomInRange(int s, int t) { srand((unsigned int)time(NULL)); return s + rand() % (t - s + 1); } void swap(int* left, int* right) { int tmp = *left; *left = *right; *right = tmp; } int partition(int data[], int length, int start, int end) { if (data == NULL || start < 0 || end >= length) throw new std::exception("invalid parameters"); int index = randomInRange(start, end); swap(&data[index], &data[end]); int small = start - 1; for (index = start; index < end; ++index) { if (data[index] < data[end]) { ++small; if (small != index) swap(&data[index], &data[small]); } } ++small; swap(&data[small], &data[end]); return small; } void quickSort1(int data[], int length, int start, int end) { if (start == end) return; int index = partition(data, length, start, end); if (index > start) quickSort1(data, length, start, index - 1); if (index < end) quickSort1(data, length, index + 1, end); } /*************************** 6 直接选择排序 ************************** 空间复杂度：只用到了i,j,k,tmp4个辅助变量，故空间复杂度为O(1). 时间复杂度：不管表的初始状态如何，比较次数都到达O(n^2),故直接选择排序的最好和最坏 时间复杂度都是O(n^2). 稳定性：不稳定，如将{5，3，2，5，4，1}排序，第1趟就改变了两个5的相对位置。可以 看成是交换排序和直接插入排序的综合，但是直接插入和冒泡排序都是稳定的，而该 算法是不稳定的 思想：每趟从待排序的记录当选择关键字最小的记录，顺序放在已排好序子表的最后，知道 全部记录排序终了 适用性：合适从大量记录当选择1部份排序记录，如从10000个记录当选择关键字大小为前10 的记录 *******************************************************************/ void selectSort(int data[], int n) { int tmp, k; for (int i = 0; i < n - 1; ++i) { k = i; for (int j = i + 1; j < n; ++j) { if (data[j] < data[k]) k = j; } if (k != i)//若k=i则证明已是有序的了 { tmp = data[i]; data[i] = data[k]; data[k] = tmp; } } } /****************************** 7 堆排序 **************************** 空间复杂度：只用到了4个辅助变量，空间复杂度是O(1). 时间复杂度：最好，最坏，和平均时间复杂度都是O(nlogn). 稳定性：不稳定 思想：本质上是1种树形选择排序思想，将原数组看成为1个完全2叉树的顺序存储结构，利 用完全2叉树中双亲节点和孩子节点之间的内在关系，在当前无序区当选择关键字 最大（大根堆）或最小（小根堆）的记录移动到数组的末尾，然后对剩余的元素作同 样的操作 适用性：不适合记录数较少的表，与直接选择排序算法类似 *******************************************************************/ //算法分为两个主要部份，堆调剂（采取挑选算法），与排序 //建立大根堆，每次将最大的元素移动到末尾 void heapAdjust(int data[], int start, int end) { int tmp = data[start]; for (int i = 2 * start + 1; i <= end; i *= 2){ //这个i data[i]) break; data[start] = data[i]; start = i; } data[start] = tmp; } void heapAdjust1(int data[], int low, int high) { int i = low, j = 2 * i+1; int tmp = data[i]; while (j <= high) { if (j < high && data[j] < data[j + 1]) ++j; if (tmp < data[j]) { data[i] = data[j]; i = j; j = 2 * i; } else break; } data[i] = tmp; } void heapSort(int data[], int n) { int i; int tmp; //建立初始堆 for (i = n / 2; i >= 0; --i) { heapAdjust(data, i, n⑴); } //堆排序进程 for (int i = n⑴; i >= 0; --i) { //交换堆顶和最后1个元素 tmp = data[0]; data[0] = data[i]; data[i] = tmp; //调剂堆满足大根堆的性质 heapAdjust(data, 0, i - 1); } } /*************************** 8 归并排序 ****************************** 空间复杂度：O(n),需要1个辅助的数组来寄存合并两个有序表以后生成的新表，故归并排序不是就地排序 时间复杂度：最好，最坏，平均时间复杂度均是O(nlogn) 稳定性：归并排序是稳定的排序算法 思想：将两个或两个以上的有序表合并为1个新的有序表，递归的思想 *******************************************************************/ ////迭代版本,有问题 //void mergeSort_iter(int data[], int n) //{ // int *b = new int[n]; // int *a = data; // //外层for循环，1共进行logn趟归并 // for (int seg = 1; seg < n; seg += seg) // { // //1趟归并排序 // for (int start = 0; start < n; start += seg + seg) // { // int low = start, mid = (start + seg) < n ? (start + seg) : n, high = (start + seg + seg) < n ? (start + seg + seg) : n; // int k = low; // int start1 = low, end1 = mid; // int start2 = mid, end2 = high; // while (start1 < end1 && start2 < end2) // b[k++] = a[start1] < a[start2] ? a[start1] : a[start2]; // while (start1 < end1) // b[k++] = a[start1++]; // while (start2 < end2) // b[k++] = a[start2++]; // } // //交换a和b // int *tmp = a; // a = b; // b = tmp; // } // //若产生交换了 // if (a != data) // { // for (int i = 0; i < n; ++i) // b[i] = a[i]; // b = a; // } // delete b; //} //1趟归并进程，将两个有序的子表合成1个新的有序表 void merge(int data[], int low, int mid, int high) { int i = low, j = mid + 1, k = 0; //临时存储排好序的数组 int *tmp = new int[high - low + 1]; while (i <= mid && j <= high) { if (data[i] < data[j]) tmp[k++] = data[i++]; else tmp[k++] = data[j++]; } while (i <= mid) tmp[k++] = data[i++]; while (j <= high) tmp[k++] = data[j++]; for (int i = low, k = 0; i <= high; i++, k++) data[i] = tmp[k]; delete tmp; } //递归情势分别对数组的左右两个子数组归并排序，然后merge成1个新的有序数组 void mergeSortR(int data[], int low, int high) { int mid; if (low < high) { mid = (low + high) / 2; mergeSortR(data, low, mid); mergeSortR(data, mid + 1, high); merge(data, low, mid, high); } } //自顶向下的2路归并排序算法 void mergeSort(int data[], int n) { mergeSortR(data, 0, n - 1); } /************************* 9 基数排序 ******************************** 空间复杂度：空间复杂度为O(n) 时间复杂度：最好、最坏、平均的时间复杂度都是O(d(n+r)),其中d是待排序元素的最大位 数，n是元素的个数，r是基数（10进制r=10，2进制r=2）。 稳定性：基数排序是稳定的排序方法 思想：通过"分配"和"搜集"进程实现排序，不需要进行关键字之间的比较，是1种借助于多 关键字排序的思想对单关键字排序的方法，分为最低位优先(LSD）和最高位优(MSD) *******************************************************************/ //辅助函数，求数据的最大位数d int maxbit(int data[], int n) { int d = 1;//保存最大位数，初始为1 int p = 10; for (int i = 0; i < n; ++i) { while (data[i] >= p) { p *= 10;//有溢出的风险 ++d; } } return d; } //基数排序 void radixSort(int data[],int n) { //得到最大位数d int d = maxbit(data, n); int *tmp = new int[n]; int *count = new int[10];//计数器 int i, j, k; int radix = 1; for (i = 1; i <= d; ++i) { //清空计数器 for (j = 0; j < 10; ++j) count[j] = 0; for (j = 0; j < n; j++) { k = (data[j] / radix) % 10;//统计每一个桶中的记录数 count[k]++; } for (j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; for (j = n - 1; j >= 0; j--) { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for (j = 0; j < n; j++) data[j] = tmp[j]; radix = radix * 10; } delete []tmp; delete []count; } void print(int data[], int n) { for (int i = 0; i < n; ++i) cout << data[i] << " "; cout << endl; } //测试 int main() { int data[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy1[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy2[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy3[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy4[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy5[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy6[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy7[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy8[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy9[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; cout << "待排序数组为： "; print(data, sizeof(data) / sizeof(int)); cout << endl << endl; cout << "1 直接插入排序： "; insertSort(copy1, sizeof(copy1) / sizeof(int)); print(copy1, sizeof(copy1) / sizeof(int)); cout << endl; cout << "2 2分插入排序： "; biInsertSort(copy2, sizeof(copy2) / sizeof(int)); print(copy1, sizeof(copy2) / sizeof(int)); cout << endl; cout << "3 希尔排序： "; shellSort(copy3, sizeof(copy3) / sizeof(int)); print(copy1, sizeof(copy3) / sizeof(int)); cout << endl; cout << "4 冒泡排序： "; bubbleSort(copy4, sizeof(copy4) / sizeof(int)); print(copy1, sizeof(copy4) / sizeof(int)); cout << endl; cout << "5 快速排序： "; quickSort(copy5, 0, sizeof(copy5) / sizeof(int)⑴); print(copy1, sizeof(copy5) / sizeof(int)); cout << endl; cout << "6 直接选择排序： "; selectSort(copy6, sizeof(copy6) / sizeof(int)); print(copy1, sizeof(copy6) / sizeof(int)); cout << endl; cout << "7 堆排序： "; heapSort(copy7, sizeof(copy6) / sizeof(int)); print(copy1, sizeof(copy7) / sizeof(int)); cout << endl; cout << "8 归并排序： "; mergeSort(copy8, sizeof(copy8) / sizeof(int)); print(copy1, sizeof(copy8) / sizeof(int)); cout << endl; cout << "9 基数排序： "; radixSort(copy9, sizeof(copy9) / sizeof(int)); print(copy1, sizeof(copy9) / sizeof(int)); cout << endl; return 0; }