1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 |
- //
- // Created by tangs on 2018/11/16.
- //
- #include <iostream>
- using namespace std;
- // 书上的实现方式,其中只能排序1 ~ n-1 个元素, 第0个元素被当做中间变量。
- void InsertSort(int A[], int n) {
- int i, j;
- for (i = 2; i < n; i++) {
- if (A[i] < A[i - 1]) {
- A[0] = A[i];
- for (j = i - 1; A[0] < A[j]; --j) {
- A[j + 1] = A[j];
- }
- A[j + 1] = A[0];
- }
- }
- }
- // 自己实现,不占用数组空间来当中间变量。
- void InsertSortBySelf(int A[], int n) {
- int i, j, temp;
- for (i = 1; i < n; i++) {
- if (A[i] < A[i - 1]) {
- temp = A[i];
- for (j = i - 1; A[j] > temp && j >= 0; j--) {
- A[j + 1] = A[j];
- }
- }
- A[j + 1] = temp;
- }
- }
- int main() {
- int A1[] = {6, 1, 5, 2, 1, 9, 10, 24, 7, 0};
- InsertSort(A1, 10);
- // print:
- // 0 0 1 1 2 5 7 9 10 24
- for (int i = 0; i < 10; i++) {
- cout << A1[i] << " ";
- }
- cout << endl;
- // --------------------------------------------------------------------------
- int A2[] = {6, 1, 5, 2, 1, 9, 10, 24, 7, 0};
- InsertSortBySelf(A2, 10);
- // print:
- // 0 1 1 2 5 6 7 9 10 24
- for (int i = 0; i < 10; i++) {
- cout << A2[i] << " ";
- }
- cout << endl;
- return 0;
- }
|