面试的三种经典排序

#include
#define MAX 6

int array[MAX];
int count = MAX;

/********创建数组，并输入元素************/
void BuildArray()
{
    int a,i=0;
    printf("请输入数组元素: ");
    for(; i    {
        scanf("%d", &a);
        array[i] = a;
    }
    printf("\n");
}

/**********遍历输出数组元素*************/
void Traverse(int arr[], int count)
{
    int i;
    printf("数组输出: ");
    for(i=0; i        printf("%d\t", arr[i]);
    printf("\n");
}

 

/*******************************************************
 冒泡排序
 算法：将相邻的两个数比较，将小的调到前头；
       有n个数，则要进行n-1趟比较，第一次比较中要进行
       n-1次两两比较，在第j趟比较要进行n-j次两两比较
********************************************************/
void BublleSort(int arr[], int count)
{
    int i,j,temp;
    for(j=0; j        for(i=0; i        {
            if(arr[i]>arr[i 1])/* 把值比较大的元素沉到底 */
            {
                temp=arr[i 1];
                arr[i 1]=arr[i];
                arr[i]=temp;
            }
        }
}

 

/*******************************************************
    插入排序
    算法： 在得到要排序的数组以后，将数组分为两部分，
          数组的第一个元素为一部分，剩下的元素为一部分，
          然后从数组的第二个元素开始，和该元素以前的所有元素比较，
          如果之前的元素没有比该元素大的，那么该元素的位置不动，
          如果有的元素的值比该元素大，那么记录下他所在的位置，
          例如为i，该元素的位置例如为k，则将从i到k位置上的
          所有元素统统向后移动，然后将k移到i元素的位置上。
          这样就找到了k所在的位置。每一个元素都这样进行，
          最终就会得到排好顺序的数组。
********************************************************/
void InsertSort(int arr[],int count)
{
    int i,j,temp;
    for(i=1; i    {
        temp = arr[i];//操作当前元素，先保存在其它变量中
        for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素
        {
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

 

/*******************************************************
 选择排序
 算法：首先以一个元素为基准，从一个方向开始扫描，
      比如从左至右扫描，以A[0]为基准。接下来从A[0]...A[9]
      中找出最小的元素，将其与A[0]交换。然后将基准位置右
      移一位，重复上面的动作，比如，以A[1]为基准，找出
      A[1]~A[9]中最小的，将其与A[1]交换。一直进行到基准位
      置移到数组最后一个元素时排序结束（此时基准左边所有元素
      均递增有序，而基准为最后一个元素，故完成排序）。
********************************************************/
void SelectSort(int arr[], int count)
{
    int i,j,min,temp;
    for(i=0; i    {
        min = arr[i];//以此元素为基准
        for(j=i 1; j        {
            if(min>arr[j])//把剩下元素中最小的那个放到arr[j]中
            {
                temp = arr[j];
                arr[j] = min;
                min = temp;
            }
        }
    }
}

int main()
{ 
    BuildArray();//创建数组
    Traverse(array, count);//输出最初数组

    BublleSort(array, count);//冒泡排序
    Traverse(array, count);//输出排序后的数组

    InsertSort(array, count);//插入排序
    Traverse(array, count);//输出排序后的数组

    SelectSort(array, count);//插入排序
    Traverse(array, count);//输出排序后的数组
    return 0;
}