几种常用排序算法

void swap(int *p1,int *p2)
{
    int temp;
    temp=*p1;
    *p1=*p2;
    *p2=temp;
}

文件:	ooo.rar
大小:	1KB
下载:	下载

#define swap(a, b) do{\

        a ^= b;\

        b ^= a;\

        a ^= b;\

}while(0) //一种新的方法

选择排序：
void select_sort(int *a,int n)
{
    int i,j,small;

    for(i=0;i<n-1;i++)
    {
        small=i;
        for(j=i+1;j<n;j++)
        {
            if(a[j]<a[small])
            {
                small=j;
            }
        }
        swap(&a[i],&a[small]);
    }
}

冒泡排序：
int bubble_sort(int *targ, int num)
{
    int i = 0, j = 0;

    for (i=0; i<(num-1); i++) {
        for (j=0; j<(num-1); j++) {
            if (targ[j] > targ[j+1])
                swap(&targ[j], &targ[j+1]);
        }
    }
}

插入排序
void insert_sort(int *a,int n)
{
    int i,j,x;

    for(i=1;i<n;i++)
    {
        x=a[i];
        j=i-1;

        while(j>=0 && a[j]>x)
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=x;

    }
}


/*
函数功能：使用快速排序法进行排序：从小到大；
函数原型：void quick_sort(int *a,int left,int right)
函数参数：int *a:数组名
          int left:排序数组的开始下标
        int right:排序数组的结束下标
*/
void quick_sort(int *a,int left,int right)
{
  int upper,low,point;
  if(left<right)
  {
      point=a[left];
      upper=right+1;
      low=left;

      while(1)
      {
          while(a[++low]<point);
          while(a[--upper]>point);
          if(low>upper)
          {
              break;
          }
          swap(&a[low],&a[upper]);
      }
      a[left]=a[upper];
      a[upper]=point;

      quick_sort(a,left,upper-1);
      quick_sort(a,upper+1,right);
  }
}

归并排序：
static void merge(int array[], int p, int q, int r)
{
    int i,k;
    int begin1,end1,begin2,end2;
    int* temp = (int*)malloc((r-p+1)*sizeof(int));
    begin1= p; end1 = q;
    begin2 = q+1; end2 = r;
       
    k = 0;
    while((begin1 <= end1)&&( begin2 <= end2))
    {
        if(array[begin1]<array[begin2])
        {
            temp[k] = array[begin1]; begin1++;
        }
        else
        {
            temp[k] = array[begin2]; begin2++;
         }
        k++;
    }
   
    while(begin1<=end1)
    {
        temp[k++] = array[begin1++];
    }
    while(begin2<=end2)
    {
        temp[k++] = array[begin2++];
    }
    for (i = 0; i < (r - p +1); i++)
        array[p+i] = temp[i];
    free(temp);
}

void merge_sort(int array[], unsigned int first, unsigned int last)
{
    int mid = 0;
    if(first<last)
    {
        mid = (first+last)/2;
        merge_sort(array, first, mid);
        merge_sort(array, mid+1,last);
        merge(array,first,mid,last);
    }
}

各种算法时间复杂度：
插入排序 ：O(n²)

冒泡排序：O(n²)

选择排序：O(n²)

快速排序：O(n log n)

归并排序：O(n log n)

 

最精确的二分查找法：

int search(int array[], int n, int v)
{
    int left, right, middle;

    left = -1, right = n;

    while (left + 1 != right)
    {
        middle = left + （right － left) / 2;

        if (array[middle] < v)
        {
            left = middle;
        }
        else
        {
            right = middle;
        }
    }

    if (right >= n || array[right] != v)
    {
        right = -1;
    }

    return right;
}