直接插入排序和快速排序

 

数组的直接插入排序和快速排序（适用于链表）

1、直接插入排序：算法思路：设一个数组（a0.........an）,把第二个值（a1）赋值给一个中间变量temp，然后第一个值（a0）与中间变量temp相比，若小于中间变量则把第一个值（a0）赋值给第二个变量，知道第二层循环的j < 0，然后把中间变量temp赋值给a[j + 1]；第二次把a[2]赋值给中间变量temp，然后依次和中间变量temp相比，若小于中间变量，则把该值赋值给它的后面一个（a[ j + 1]），直到 j < 0，然后把中间变量赋值给a[ j + 1]；。。。。。。。。依次这样循环，直到第一层循环结束。

2、快速排序法：算法思路：设记录的Key集合K = {50， 36， 66， 76， 36， 12， 25， 95}，每次以集合的第一个Key为基准相比较，把数组a传以及其中的low（最开始传的是0）和high（数组的最大值减1）传给被调函数，然后把a[low]赋值给中间变量temp，?之后先从右边的值与中间变量相比较，直到右边的某个值a[ j ]小于中间变量，然后在把这个值赋值给a[ i ]，?然后再从左到右一次与中间变量temp相比较，直到某个值大于中间变量，再把a[ i ]赋值给a[ j ]，再回到?。。。。。这样一次循环，直到i  <  j。然后在分别递归调用中间变量左边和右边的那些数。

#include "stdio.h"

#define MAXSIZE 10

/*直接插入排序*/

void insert_sort(int *a, int len)

{

       int temp;

       int i, j;

       for(i=1; i

       {

              temp = a[i];

              for(j=i-1; temp=0; j--)

              {

                     a[j+1] = a[j];

              }

              a[j+1] = temp;

       }

}

/*快速排序*/

void quick_sort(int *a, int low, int high)

{

       int i = low, j = high;

       int temp;

       if(i < j)//这个if判断用于递归结束

       {

              temp = a[low];

              while(i < j)   //这个while循环是第一次把小于a[low]的数放在左边，把大于a[high]的数放在右边

              {

                     while(i

                            j--;

                     if(i

                            a[i] = a[j];

                     while(i=a[i])

                            i++;

                     if(i

                            a[j] = a[i];

              }   

              a[i] = temp;//这里就是相当与分界线                 

              quick_sort(a,low,i-1);//利用递归的思想把a[low]左边的数再排序，直到i = j

              quick_sort(a,i+1,high);//利用递归的思想把a[low]右边的数再排序，直到i = j

       }

}

int len(int *data)

{

       int sum = 0;

       while(*data++)

       {

              sum++;

       }

       return sum;

}

void display(int *data, int len)

{

       int i;

       for(i = 0; i < len; i++)

       {

              printf("%d  ",*data++);

       }

       putchar('\n');

}

int main()

{

       int data[MAXSIZE] = {2,5,3,6,9,1,7};

       display(data,len(data));

       insert_sort(data, len(data));//这里是按照直接插入排序的方式在排序

       //quick_sort(data,0,len(data)-1);//这里是按照快速排序的方式在排序

       display(data,len(data));

       return 0;

}