/* * 如果待排序的表中,存在多个关键字相同的元素,经过排序后 * 这些具有相同关键字的元素之间的相对次序保持不变,则称这种 * 排序方法是稳定的。反之,如果具有相同关键字的元素之间的相 * 对次序发生变化,则称这种排序方法是不稳定的。 */ /* * 1.插入排序:假设待排序的元素存放在R[0, n-1]中,怕徐过程中的某一时刻,R * 被划分为两个子区间R[0,i-1]和R[i,n-1](刚开始i = 1,有序区只有R[0]一个元素), * 其中,前一个子区间是已经排好序的有序区,后一个子区间是当前未排序的地方,不妨称其 * 为无序区。直接插入排序的一趟操作是将当前无序区的头元素R[i](1<=i<=n-1)插入到有序区 * R[0,i-1]中的适当的位置上,使得R[0,i]变为新的有序区。 * 时间复杂度O(n^2),是一种稳定排序。 */ void InsertSort(int R[], int length) { int i, j; int tmp; for (i = 1; i < length; i++) { tmp = R[i]; j = i - 1; while (j >= 0 && tmp < R[j]) { R[j + 1] = R[j]; j--; } R[j + 1] = tmp; } } /* * 2.折半插入排序:直接插入排序将无序区中开头元素R[i](1<=i<=n-1)插入到有序区R[0,i-1] * 中,此时可以采用折半查找方法现在R[0,i-1]中找到插入的位置,再通过移动元素进行插入。 * 时间复杂度O(n^2),是一种稳定排序。 * 就平均性能而言,折半查找优于顺序查找,所以折半插入排序也优于直接插入排序。 */ void InsertSort(int R[], int length) { int i, j, low, high, mid; int tmp; for (i = 1; i < length; i++) { tmp = R[i]; low = 0, high = i - 1; while (low <= high) { mid = (low + high) / 2; if (tmp < R[mid]) { high = mid - 1; } else { low = mid + 1; } } for (j = i - 1; j >= high + 1; j--) { R[j + 1] = R[j]; } R[j + 1] = tmp; } } /* * 3.冒泡排序:通过无序区中相邻元素关键字的比较和位置的交换,使得关键字最小的元素如气泡 * 一般逐渐上浮,直到“水面”。整个算法是从最下面的元素开始,对每两个相邻的关键字进行比较, * 且使关键字较小的元素换至关键字较大的元素之上,使得经过一趟冒泡排序后,关键字最小的元素 * 到达最上端。接着,再在剩下的元素中找关键字次小的元素,并把它换到第二个位置上。依次类推, * 直到所有的元素有序为止。 * 时间复杂度O(n^2), 是一种稳定排序 */ void BubbleSort(int R[], int n) { int i, j; int tmp; for (i = 0; i < n - 1; i++) { for (j = n - 1; j > i; j--) { if (R[j] < R[j - 1]) { tmp = R[j]; R[j] = R[j - 1]; R[j - 1] = tmp; } } } } /* * 在某一趟比较时没有出现任何元素的交换,就说明已经排好序了,就可以结束了。 */ void BubbleSort(int R[], int n) { int i, j; bool exchange; int tmp; for (i = 0; i < n - 1; i++) { exchange = false; for (j = n - 1; j > i; j--) { if (R[j] < R[j - 1]) { tmp = R[j]; R[j] = R[j - 1]; R[j - 1] = tmp; exchange = true; } } if (!exchange) { return; } } } /* * 4.快速排序:在待排序的n个元素中任取一个元素(通常取第一个元素)作为基准, * 把该元素放入适当的位置后,数据序列被此元素划分为两部分,所有关键字比 * 该元素关键字小的元素放置在前一部分,所有关键字比它大的元素放置在后一 * 部分,并把该元素排在这两部分的中间(称该元素归位),这个过程称作一趟快速 * 排序,之后对所有划分出来的两部分分别重复上述过程,直至每部分内只有一个 * 元素或为空为止。简而言之,每趟将表的第一个元素放入适当位置,将表一分为二, * 对子表按递归方式继续这种划分,直到划分的子表长为1或0。 * 最坏的时间复杂度是O(n^2),最好的时间复杂度为O(nlog2 n)。不稳定的排序算法。 */ void QuickSort(int R[], int s, int t) { int i = s, j = t; int tmp; if (s < t) { tmp = R[s]; while (i != j) { while (j > i && R[j] >= tmp) j--; R[i] = R[j]; while (j > i && R[i] <= tmp) i++; R[j] = R[i]; } R[i] = tmp; QuickSort(R, s, i - 1); QuickSort(R, i + 1, t); } } /* * 5.选择排序:第i趟排序开始时,当前有序区和无序区分别为R[0,i-1]和R[i,n-1]。该趟排序时从无序区中选出关键字 * 最小的元素R[k],将它与无序区的第一个元素交换,使R[0,i]和R[i+1,n-1]分别变为新的有序区和新的无序区。每趟 * 排序均使有序区增加一个元素,无序区减少一个元素,直到结束。 * 时间复杂度O(n^2),不稳定的排序算法。 */ void SelectSort(int R[], int n) { int i, j, k; int tmp; for (i = 0; i < n - 1; i++) { k = i; for (j = i + 1; j < n; j++) { if (R[j] < R[k]) { k = j; } } if (k != i) { tmp = R[i]; R[i] = R[k]; R[k] = tmp; } } } /* * 6. 归并排序:归并排序是多次将两个或两个以上的有序表合成一个新的有序表。最简单的归并是直接将 * 两个有序的子表合并成一个有序的表即二路归并。将R[0,n-1]看成n个长度为1的有序序列,然后进行两两 * 归并,然后再进行归并,直到得到长度为n的有序序列。 * 时间复杂度O(nlog2 n), 稳定排序算法。 * */ void Merge(int R[], int low, int mid, int high) { int* R1; int i = low, j = mid + 1, k = 0; R1 = new int[high - low + 1](); while (i <= mid && j <= high) { if (R[i] < R[j]) { R1[k] = R[i]; i++; k++; } else { R1[k] = R[j]; k++; j++; } } while (i <= mid) { R1[k] = R[i]; k++; i++; } while (j <= high) { R1[k] = R[j]; j++; k++; } for (k = 0, i = low; i <= high; k++, i++) { R[i] = R1[k]; } delete[] R1; R1 = nullptr; } //对整个表进行一趟归并 void MergePass(int R[], int length, int n) { int i; for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length) //归并length长的两个相邻子表 { Merge(R, i, i + length - 1, i + 2 * length - 1); } if (i + length - 1 < n) // 余下两个子表,后者长度小于length { Merge(R,i, i + length - 1, n - 1); //归并这两个子表 } } void MergeSort(int R[], int n) //自底而上的两路归并算法 { int length; for (length = 1; length < n; length = 2 * length) { MergePass(R, length, n); } }