`

部分排序算法c语言实现

 
阅读更多

代码比较粗糙,主要是用于对排序算法的理解,因而忽略了边界和容错处理相关代码。

 

相关文档:

Insert Sort  ,Bubble Sort ,Select Sort ,Shell sort ,Quick sort ,Heap sort ,Merge sort on Wikipedia

algorithm Repository :C语言实现部分排序算法,代码质量较高,其实现类似于库函数

sorting and searching algorithms :点击左边的链接即可查看整份文档

排序算法性能比较:图片链接

插入,选择,冒泡排序的算法复杂度为O(n^2)

希尔排序(shell sort)的算法复杂度因所采用增量序列的不同而有很大差别,例如shell增量序列(1,2,..,2^k)的算法复杂度可能达到O(n^2),其他增量序列则为O(n^1.5)到O(n^(7/6))不等,但其算法复杂度不可能达到O(nlogn);

快速排序,堆排序,归并排序算法复杂度为O(nlogn)。

快速排序虽然被认为是最快的,但是写一个完全正确的算法却并不容易(即在任何情况下算法复杂度均为O(nlogn)),感兴趣的可以看看glibbsd 的快速排序实现,有一篇论文《engineering a sort function 》中也写了qsort的实现

包含三个文件:

sort.c:

/* to compiler the program, use: gcc -o sort sort.c misc.c -g -Wall
/* insert sort */
#include <stdio.h>
#include <stdlib.h>
#include "misc.h"

int insertSort(int a[], int n);
int shellSortSh(int a[], int n);
int shellSortHi(int a[], int n);
int shellSortKn(int a[], int n);
int bubSort(int a[], int n);
int selectSort(int a[], int n);
int median3(int a[], int n);
int quickSort(int a[], int n);
int heapify(int a[],int i, int n);
int heapSort(int a[], int n);
int mergeArray(int a[],int splitIndex,int n);
int mergeSort(int a[], int n);
/*
void testMedian3()
{
  int a[3] = {3,2,1};
  int len = ARRLEN(a);

  median3(a,len);
  printArray(a,len);
  }*/
int main(void)
{
  int a[] = {8,1,4,9,6,3,5,2,7,0};
  /*  int a[] = {5,7,3,8};*/
  int len = ARRLEN(a);
  /*  testSort(a,len,insertSort);*/
  /*  testSort(a,len,shellSortKn);*/
  testSort(a,len,mergeSort);
  /*  testMedian3();*/
  return 0;
}
int insertSort(int a[], int n)
{
  int i,j;
  int tmp;
  for(i = 0; i < n; i++)
    {
      tmp = a[i];
      for(j = i; j > 0 && a[j-1] > tmp; --j)
	  a[j] = a[j-1];
      a[j] = tmp;
      /*      printArray(a,n);*/
    }
  return 0;
}
/* the origin shell sort by Shell using increment sequence
   of n/2,n/4 ... 1 */
int shellSortSh(int a[], int n)
{
  int i,j;
  int inc;
  int tmp;
  
  for(inc = n/2; inc > 0; inc /= 2)
    for(i = inc; i <n; i++)
      {
	tmp = a[i];
	for(j = i; j >= inc && tmp < a[j-inc]; j -= inc)
	  a[j] = a[j-inc];
	a[j] = tmp;
	printArray(a,n);
      }
  return 0;
}
/* shell sort by Hibbard's sequence:
   2^k-1,...,7,3,1 */
int shellSortHi(int a[],int n)
{
  int i,j;
  int inc;
  int tmp;
  for(inc = 1; inc < n/2; inc = 2*inc+1) ;
  for( ; inc > 0; inc /= 2)
    for(i = inc; i <n; i++)
      {
	tmp = a[i];
	for(j = i; j >= inc && tmp < a[j-inc]; j -= inc)
	  a[j] = a[j-inc];
	a[j] = tmp;
	printArray(a,n);
      }
  return 0;
}
/* Shell sort using knuth's sequence:
   (3^k-1)/2,...,13,4,1 */
int shellSortKn(int a[], int n)
{
  int i,j;
  int inc;
  int tmp;
  for(inc = 1; inc < n/3; inc = 3*inc+1) ;
  for( ; inc > 0; inc /= 3)
    for(i = inc; i <n; i++)
      {
	tmp = a[i];
	for(j = i; j >= inc && tmp < a[j-inc]; j -= inc)
	  a[j] = a[j-inc];
	a[j] = tmp;
	printArray(a,n);
      }
  return 0;
}
/*for shell sort there is also a Sedgewick's sequence: 
  1,5,19,41,...
 which can be constructed by:
 1,19,104,505,...,9(4^k-2^k)+1, k=0,1,2,3,...
 5,41,209,929,...,(2^(k+2))*(2^(k+2)-3)+1, k = 0,1,2,3,.. */

/*bubble sort */
int bubSort(int a[], int n)
{
  int i,j,tmp;
  for(i = n-1; i >= 0; --i)
    for(j = 0;  j < i; j++)
      if(a[j] >a[j+1])
	{
	  tmp = a[j];
	  a[j] = a[j+1];
	  a[j+1] = tmp;
	}
  return 0;
}
/* select sort */
int selectSort(int a[], int n)
{
  int i,j;
  int minIndex,minNum;
  for(i = 0; i < n; i++)
    {
      minIndex = i;
      minNum = a[i];
      for(j = i+1; j < n; j++)
	if(a[j] < minNum)
	  {
	    minIndex = j;
	    minNum = a[j];
	  }
      a[minIndex] = a[i];
      a[i] = minNum;
    }
  return 0;
}
/* partition function to find a element to cut an array to two pieces */
/* This function is used by quick sort function */
int median3(int a[], int n)
{
  int mid = n/2-1;

  /* the following three sentences make sure that
     a[0] <= a[mid] <= a[n-1] */
  if(a[0] > a[mid])
    swap(&a[0],&a[mid]);
  if(a[0] > a[n-1])
    swap(&a[0],&a[n-1]);
  if(a[mid] > a[n-1])
    swap(&a[mid],&a[n-1]);

  /* exchange elemments to set the pivot at the beginning of array */
  swap(&a[0],&a[mid]);
  return a[0];
}
/* quick sort */
int quickSort(int a[], int n)
{
  int low = 1, high = n-1;
  int pivot;
  printArray(a,n);
  if(n <= 3)
    {
      insertSort(a,n);
      return 0;
    }
  pivot = median3(a,n);
  while(low < high)
    {
      while(a[low] < pivot) low++;
      while(a[high] > pivot) high--;
      if(low < high)
	swap(&a[low],&a[high]);
      else
	break;
      /*      printArray(a,10);*/
    }
  swap(&a[0],&a[low-1]);
  quickSort(a,low-1);
  quickSort(a+low,n-low);
  return 0;
}
int heapify(int a[], int i, int n)
{
    int maxIndex = i;
    int lChild = 2*i+1,rChild = lChild+1;
    if(lChild < n && a[lChild] > a[maxIndex])
        maxIndex = lChild;
    if(rChild < n && a[rChild] > a[maxIndex])
        maxIndex = rChild;
    if(maxIndex != i)
    {
        swap(&a[maxIndex],&a[i]);
        heapify(a,maxIndex,n);
    }
    return 0;
}
int heapSort(int a[], int n)
{
    int i;
    for(i = (n-1)/2; i >= 0; i--)
        heapify(a,i,n);
    for(i = n-1; i >0; i--)
    {
        swap(&a[i],&a[0]);
        heapify(a,0,--n);
    }
    return 0;
}
int mergeArray(int a[], int splitIndex, int n)
{
    int *tmpArray = malloc(n*sizeof(int));
    int i ,left,right;
    i = left= 0;right = splitIndex;
    while(left < splitIndex && right < n)
    {
       if(a[left] <= a[right])
           tmpArray[i++] = a[left++];
       else
           tmpArray[i++] = a[right++];
    }
    while(left < splitIndex)
        tmpArray[i++] = a[left++];
    while(right < n)
        tmpArray[i++] = a[right++];
    for(i = 0; i < n; i++)
        a[i] = tmpArray[i];
    return 0;
}
int mergeSort(int a[], int n)
{
    int mid;
    if(n > 1)
    {
        mid = n/2;
        mergeSort(a,mid);
        mergeSort(a+mid,n-mid);
        mergeArray(a,mid,n);
    }
    return 0;
}
 

misc.c:

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

void fillArray(int a[], int n)
{
  int i;
  srand(time(NULL));
  for(i = 0; i < n; i++)
    a[i] = rand();
}
void printArray(int a[], int n)
{
  int i;
  printf("%d",a[0]);
  for(i = 1; i < n; i++)
    printf(" %d",a[i]);
  printf("\n");
}
void testSort(int a[], int n, int (*sort)(int a[], int n))
{
  printf("the initial array is:\n");
  printArray(a,n);
  sort(a,n);
  printf("\nAfter sorting,the array is:\n");
  printArray(a,n);
}
void swap(int *x, int *y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

 misc.h:

#ifndef MISC_H
#define MISC_H

#define ARRLEN(a) (sizeof(a)/sizeof(a[0]))
void fillArray(int a[], int n);
void printArray(int a[], int n);
void testSort(int a[], int n, int (*sort)(int a[], int n));
void swap(int *x, int *y);
#endif
 
分享到:
评论

相关推荐

    堆排序算法 C语言实现

    C语言实现的堆排序算法。 提供了堆排序算法的一个接口,可以为其它功能提供功能。

    冒泡,选择,插入排序算法c语言实现

    冒泡排序算法选择排序算法插入排序c语言实现

    二分法排序算法 C语言实现

    根据给定的文件信息,我们可以总结出以下关于“二分法排序算法C语言实现”的相关知识点: ### 1. 二分法搜索算法原理 二分法搜索算法,也称为折半查找算法,是一种在有序数组中查找特定元素的搜索算法。其基本思想...

    常用排序算法C语言实现

    本资源"常用排序算法C语言实现"提供了一个实践平台,帮助学习者将理论知识转化为实际代码。 首先,让我们探讨几种常见的排序算法及其C语言实现: 1. **冒泡排序(Bubble Sort)**:冒泡排序是最基础的排序方法,...

    八大排序算法C语言

    本资料“八大排序算法C语言”聚焦于八种常见的排序算法,每种都有C语言实现,这对于理解和实践这些算法非常有帮助。 1. **冒泡排序**:冒泡排序是一种简单的交换排序,通过不断遍历数组并交换相邻的逆序元素来逐步...

    几种常用排序算法的C语言实现

    一些常用排序算法的C语言实现,包括直接选择排序,希尔排序,直接插入排序,快速排序,归并排序,冒泡排序,堆排序

    算法:C语言实现(第1~4部分)答案

    在本资源中,我们主要关注的是使用C语言实现算法的解答,这涵盖了算法的第1到第4个部分。C语言是一种广泛用于系统编程、应用编程、嵌入式系统以及编写算法实现的强大编程语言。其简洁性和高效性使得它成为学习和理解...

    快速排序算法C语言实现

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治策略,即将一个大问题分解为小问题来解决。在这个案例中,我们关注的是如何用C语言实现快速排序。 快速排序的步骤...

    基本排序算法C语言实现

    本资源“基本排序算法C语言实现”提供了一系列经典的排序算法的C语言实现,帮助开发者深入理解这些算法的工作原理并能实际运用到项目中。 1. **冒泡排序**: 冒泡排序是一种简单的排序算法,它重复地遍历要排序的...

    快速排序算法 C语言实现

    快速排序算法 C语言实现 快速排序算法是一种高效的排序算法,通过递归的方式将记录分区排序。下面将详细介绍快速排序算法的实现细节。 首先,我们需要了解快速排序算法的基本思想。快速排序算法的核心思想是选择一...

    归并排序算法C语言实现

    完整的实现了归并排序的算法,使用C语言实现,相信看过本程序之后,会对归并排序了如指掌

    归并排序算法C语言版

    归并排序算法C语言版

    堆排序算法c语言实现

    学习堆排序时自己编的代码,里面有自动生成随机数的代码段方便大家测试

    各种常用排序算法的C语言实现

    本资源提供了各种常用排序算法的C语言实现,源自严蔚敏的经典教材《数据结构》。下面将详细介绍这些排序算法及其在C语言中的实现原理。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序方法,通过不断交换相邻...

    算法C语言实现(第1-4部分).zip

    在本压缩包“算法C语言实现(第1-4部分).zip”中,包含的是关于算法的详细实现,使用了C语言这一经典编程语言。C语言以其高效、灵活和接近硬件的特点,常被用于编写算法代码,特别是对于数据结构和算法的底层实现,它...

    算法:C语言实现(第5部分).pdf

    排序算法是算法学习的基础,书中可能会详细介绍各种排序算法,如冒泡排序、选择排序、插入排序、快速排序、归并排序等,并通过C语言实现。这些算法各有优劣,适用于不同场景。例如,快速排序因其高效性而广泛应用于...

    经典算法 C语言实现

    经典算法通常指的是那些在计算机科学中被广泛研究、具有普遍意义并被广泛应用的算法,例如排序算法(如冒泡排序、快速排序、归并排序)、搜索算法(如二分查找、深度优先搜索、广度优先搜索)以及数据结构(如栈、...

    算法C语言实现(第1~4部分)

    根据给定文件的信息,《算法:C语言实现(第1~4部分)基础知识、数据结构、排序及搜索》这本书主要聚焦于使用C语言来实现各种算法和数据结构。这是一本非常实用且深入浅出的计算机科学教材,对于学习者来说,能够帮助...

    排序算法C语言实现

    排序算法,包括典型的排序,起泡法、快速排序、选择排序等等

    算法:算法C语言实现 第1-4部分 基础知识、数据结构、排序及搜索

    算法:C语言实现 (第1-4部分)基础知识、数据结构、排序及搜索(原书第3版) 本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分,共16章。第一部分“基础知识”(第1—2章)介绍基本算法分析原理。...

Global site tag (gtag.js) - Google Analytics