插入排序的递归算法

插入排序算法： C版本的分析如下：

//直接插入排序：从小到大排；

//算法说明： 比如说现在排序进行到第 i位了，那么1 到 i-1位都已经为有序序列了；然后将 r[0]和r[j]依次比较，若是r[j]>r[0],那么就依次用前边数据覆盖后边数据，不必担心r[i]会丢掉，因为它被保存在了r[0]中，直到找到满足r[i]<r[j]的位置,将r[0]数据写入r[j]处，一次循环结束，进入下次循环；

void insSort( int r[],int length) //传数组，和数组大小；

{

// 数组下标从1 开始， 0号位为监视哨；

int i=0,j=0

for(i=2i<=length++i)

{

r[0]=r[i] //总是用r[0]记录当前数据；

j=i-1

while(r[0]<r[j]) //寻找合适的位置；

{

r[j+1]=r[j] //依次迭代覆盖；

j=j-1

}

r[j+1]=r[0] //晕，终于找到满足条件的地方了，赶紧钻入；

}

}

大功告成！ 希望能帮上你。。。

//InsertionSort

void insertionSort(int a[], int size) {

int i, j, key

for (i = 0i <sizei++) {

key = a[i]

j = i-1

while (j >= 0 &&key <a[j]) { //把元素插入到之前的有序元组中

a[j+1] = a[j]

j--

}

a[j+1] = key

}

}

//MergeSort

void merge(int a[], int p, int q, int r) { //合并两个子元组

int i, j, k, n1, n2

int *array1, *array2

n1 = q - p + 1,

n2 = r - q

array1 = (int *)calloc(n1+1, sizeof(int))

array2 = (int *)calloc(n2+1, sizeof(int))

if (array1 == NULL || array2 == NULL) {

printf("Error: calloc failed in concat\n")

exit(EXIT_FAILURE)

}

for(i = 0i <n1i++)

array1[i] = a[p + i]

for(i = 0i <n2i++)

array2[i] = a[q + 1 + i]

array1[n1] = MAXNUMBER

array2[n2] = MAXNUMBER

i = 0, j = 0

for(k = pk <= rk++)

if(array1[i] <= array2[j])

a[k] = array1[i++]

else

a[k] = array2[j++]

free(array1)

free(array2)

}

void mergeSort(int a[], int p, int r) {//归并的递归调用

int q

if (p <r) {

q = (p+r)/2

mergeSort(a,p,q)

mergeSort(a,q+1,r)

merge(a,p,q,r)

}

}

//QuickSort

int partition(int a[], int p, int r) {//快排的分组函数

int i, j, x, temp

x = a[r]

i = p - 1

for (j = pj <rj++)

if (x >a[j]) {

temp = a[++i]

a[i] = a[j]

a[j] = temp

}

temp = a[++i]

a[i] = a[r]

a[r] = temp

return i

}

void quickSort(int a[], int p, int r) { //快排

int q

if (p <r) {

q = partition(a, p, r)

quickSort(a, p, q-1)

quickSort(a, q+1, r)

}

}

//随即版的quickSort

int randomPartition(int a[], int p, int r){

int i, temp

i = rand()

while( i <p || i >r)

i = rand()

temp = a[i]

a[i] = a[r]

a[r] = temp

return partition(a,p,r)

}

void randomQuickSort(int a[], int p, int r){

int q

if(p <r){

q = randomPartition(a,p,r)

randomQuickSort(a,p,q-1)

randomQuickSort(a,q+1,r)

}

}

//BubbleSort()//冒泡排序

void bubbleSort(int a[], int size) {

int i, j, temp

for (i = size -1i >= 0i--)

for (j = 0j <ij++)

if (a[j] <a[j+1]) {

temp = a[j]

a[j] = a[j+1]

a[j+1] = temp

}

}

---