排序集锦

  冒泡和选择排序



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//冒泡排序

void bubbleSort(int *a,int len)
{
     int i,j,temp;
     for(i = 0;i<len-1;i++)
     {
          for(j=0;j<len -i-1;j++)
          {
               if(a[j]>a[j+1])
               {
                   temp=a[j];
                   a[j]=a[j+1];
                   a[j+1]=temp;
               }
         }
    }
}
//选择排序

void selectSort(int *a,int len)
{
     int i,j,temp,result;
     for(i=0;i<len-1 ;i++)
     {
          temp=i;
          for(j=i+1;j<len-1;j++)
          {
                if(a[j]<a[temp])
                {
                       temp=j;
                }
         }
         if(temp!=i)
          {
               result=a[i];
               a[i]=a[temp];
               a[i]=result;
          }
     }
}

void print(int *a,int len)
{
    int i=0;
    for(i=0;i<len;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}


int main()
{
    int value[10]={38,6,14,9,7,33,67,12,34,51};
    printf("bubbleSort result:\n");
    bubbleSort(value,10);
    print(value,10);
    printf("bubbleSort result:\n");
    selectSort(value,10);
    print(value,10);
    return 0;

}

快速排序

//快速排序，主要思想是通过一趟排序将待排序的记录分割成相邻的两个区域，

//其中一个区域中的关键字均比另一区域中记录的关键字要小，在分别对这两个

//区域进行排序，以达到整个序列有序。一般情况是O(logn),最坏情况是O(n)


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10

int QSorting(int *result ,int first,int end)
{
     int key = result[first];
     while(first < end)
     {
          while(first < end&&result[end] >= key)
          end--;
          if(first != end)
                result[first++] = result[end];
          while(first < end && result[first] <= key)
               first++;
          if(first != end)
               result[end--] = result[first];
      }
      result[first] = key;
      return first;
}


void Qsort(int *result,int first,int end)
{
     if(first < end )
     {
             int middle = QSorting(result,first,end);
             Qsort(result,first,middle-1);
             Qsort(result,middle+1,end);
     }
}

int main()
{
     int value[N] = {18,94,61,87,34,31,78,56,14,17};
     int i = 0;
     int sum = 0;
     Qsort(value,0,N-1);
     for(i = 0 ;i < N;i++)
     {
          sum = sum + value[i];
          printf("%d\n",value[i]);
      }
      printf("the result:%d\n",value[N/2]-sum/N);
      return 0;
}

二分查找算法

二分查找算法是基于已经排好序的数列。这是它的实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//二分法查找


int find(int *result,int key,int len)
{
 int first,end,mid;
 first=0;
 end=len-1;
 while(first<=end)//注意这里的等于

 {
  mid=(first+end)/2;
  if(result[mid]==key)
  {
   return 1;
  }
  else if(result[mid]>key)
  {
   end=mid-1;
  }
  else
  {
   first=mid+1;
  }
 }
 return 0;

}

int main()
{
 int value[10]={1,2,3,4,5,6,7,8,9,10};
 int res=find(value,4,10);
 printf("%d\n",res);

 return 0;
}