插入排序

今天在图书馆无意借到一本写scheme的书，随手翻了翻，没学过lisp感觉很特别，里面有一段排序的代码，挺有意思的，顺手用C++改写了下，原scheme程序如下：

(define (sort alon)

(cond

[empty alon) empty]

[else (insert (first alon)(sort (rest alon)))]))

(define (insert n alon)

(cond

[(empty? alon) ...]

[else ... (first alon) ... (insert n (rest alon)) ...]))

=============================================================

(define (a-sort a-list)
  (cond
    [(empty? a-list) empty]
    [else (insert (first a-list ) (a-sort (rest a-list)))]))
   
(define (insert a a-list)
  (cond
    [(empty? a-list) (cons a empty)]
    [else (cond
            [(< a (first a-list)) (cons (first a-list)(insert a (rest a-list)))]
            [else (cons a a-list)])]))

根据这段程序，我们也可以写两个函数来实现排序，sort 和 insert：

 

//============================================================================

// Name : sort.cpp

// Author : Rick

// Version :

// Copyright : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================


#include <iostream>
using namespace std;
void sort(int array[], int n);
void insert(int *p, int array[], int n);
int main() {
    int a[10]={1,3,7,4,5,6,7,8,9,0};
    sort(a,10);
    for(int i=0;i<10;i++)
        cout<<a[i]<<endl;
    return 0;
}

void sort(int array[], int n) {
    if (n <= 2) {
        if (array[0] < array[1]) {
            int temp = array[0];
            array[0] = array[1];
            array[1] = temp;
        }
    } else {
        sort(array + 1, n - 1);
        insert(array, array + 1, n - 1);
    }
}
void insert(int *p, int array[], int n) {
    if (n > 1) {
        if (*p < array[0]) {
            int temp = *p;
            *p = array[0];
            array[0] = temp;
            insert(array, array + 1, n - 1);
        }
    } else {
        if (*p < array[0]) {
            int temp = *p;
            *p = array[0];
            array[0] = temp;
        }
    }
}

排序的效果还不错，只是复杂度不知道是多少。。。。