经典排序算法

经典排序算法



创建3个文件：sortArray.h、sortArray.c、sortArrayTest.c。



sortArray.h 
#ifndef SORT_ARRAY_H_
#define SORT_ARRAY_H_

// 功能: 比较两个数据.
// 参数: a(数据a), b(数据b).
// 返回: a>b返回正数, a<b返回负数, 否则返回0.
// 注意: 其实返回值可以是任意int类型值, 但是为了统一规范使用所以才强制返回值.
typedef int ( CompareFunc )( const void *a, const void *b );

// 功能: 选择排序.
// 参数: a(需排序的数组), left(需排序区间的左闭边界), right(需排序区间的右闭边界), cmp(自定义比较函数).
// 返回: 无.
// 注意: 当 a 为NULL 或 cmp 为NULL 或 区间范围表示错误 时, 将错误退出程序.
extern void selectSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp );

// 功能: 冒泡排序.
// 参数: a(需排序的数组), left(需排序区间的左闭边界), right(需排序区间的右闭边界), cmp(自定义比较函数).
// 返回: 无.
// 注意: 当 a 为NULL 或 cmp 为NULL 或 区间范围表示错误 时, 将错误退出程序.
extern void bubbleSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp );

// 功能: 插入排序.
// 参数: a(需排序的数组), left(需排序区间的左闭边界), right(需排序区间的右闭边界), cmp(自定义比较函数).
// 返回: 无.
// 注意: 当 a 为NULL 或 cmp 为NULL 或 区间范围表示错误 时, 将错误退出程序.
extern void insertSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp );

// 功能: 归并排序.
// 参数: a(需排序的数组), left(需排序区间的左闭边界), right(需排序区间的右闭边界), cmp(自定义比较函数).
// 返回: 无.
// 注意: 当 a 为NULL 或 cmp 为NULL 或 区间范围表示错误 时, 将错误退出程序.
extern void mergeSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp );

// 功能: 快速排序.
// 参数: a(需排序的数组), left(需排序区间的左闭边界), right(需排序区间的右闭边界), cmp(自定义比较函数).
// 返回: 无.
// 注意: 当 a 为NULL 或 cmp 为NULL 或 区间范围表示错误 时, 将错误退出程序.
extern void quickSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp );

// 功能: 堆排序.
// 参数: a(需排序的数组), left(需排序区间的左闭边界), right(需排序区间的右闭边界), cmp(自定义比较函数).
// 返回: 无.
// 注意: 当 a 为NULL 或 cmp 为NULL 或 区间范围表示错误 时, 将错误退出程序.
extern void heapSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp );

// 功能: 计数排序.
// 参数: a(需排序的数组), left(需排序区间的左闭边界), right(需排序区间的右闭边界), cmp(自定义比较函数).
// 返回: 无.
// 注意: 当 a 为NULL 或 cmp 为NULL 或 区间范围表示错误 时, 将错误退出程序.
extern void countSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp );

// 功能: 基数排序.
// 参数: a(需排序的数组), left(需排序区间的左闭边界), right(需排序区间的右闭边界), cmp(自定义比较函数).
// 返回: 无.
// 注意: 当 a 为NULL 或 cmp 为NULL 或 区间范围表示错误 时, 将错误退出程序.
extern void radixSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp );

#endif

sortArray.c 
#include <stdint.h>
#include <time.h>
#include "sortArray.h"


// 功能: 打印错误信息后就错误退出程序.
// 参数: expression(错误判断表达式), message(需打印的错误信息).
// 返回: 无.
// 注意: 当表达式 expression 为真时, 才触发.
#define ERROR_EXIT( expression, message )                                    
if( (expression) ) {                                                         
	fprintf( stderr, "
error location: file = %s, func = %s, line = %d.
", 
	                       __FILE__, __func__, __LINE__ );                   
	fprintf( stderr, "error  message: %s%s.
a",                            
	                       (message) != NULL ? (message) : __func__,         
		                   (message) != NULL ? "" : " function error" );     
	exit( EXIT_FAILURE );                                                    
}

// 功能: 数组的两个元素进行互换.
// 参数: a(数组首地址), i(数组下标), j(数组下标).
// 返回: 无.
// 注意: 没有副作用的宏, C99标准: #define f ({...}).
#define SWAP( a, i, j ) ({            
	int32_t i1i1i = (i), j1j1j = (j); 
	int32_t t1t1t = *((a) + i1i1i);   
	*((a) + i1i1i) = *((a) + j1j1j);  
	*((a) + j1j1j) = t1t1t;           
})

#define MAX( a, b ) ((a) > (b) ? (a) : (b))
#define MIN( a, b ) ((a) < (b) ? (a) : (b))
  • selectSortArray 
    void selectSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, m = 0;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	while( left <= right ) {
		m = left;
		for( i = left + 1; i <= right; ++i ) {
			m = cmp( &a[i], &a[m] ) < 0 ? i : m;
		}
		if( m != left ) {
			SWAP( a, left, m );
		}
		++left;
	}
}

  • bubbleSortArray 
    void bubbleSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	while( left < right ) {
		for( i = right; i > left; --i ) {
			if( cmp( &a[i], &a[i - 1] ) < 0 ) {
				SWAP( a, i, i - 1 );
			}
		}
		++left;
	}
}

  • insertSortArray
    • 版本一 
      void insertSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, j = 0;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	for( i = left; i < right; ++i ) {
		#if 1
		for( j = i + 1; j > left && cmp( &a[j], &a[j - 1] ) < 0; --j ) {
			SWAP( a, j, j - 1 );
		}
		#else
		for( j = i; j >= left && cmp( &a[j + 1], &a[j] ) < 0; --j ) {
			SWAP( a, j, j + 1 );
		}
		#endif
	}
}
    • 版本二 
      void insertSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, j = 0, temp = 0;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	for( i = left; i <= right; ++i ) {
		temp = a[i];
		for( j = i - 1; j >= left && cmp( &temp, &a[j] ) < 0; --j ) {
			a[j + 1] = a[j];
		}
		a[j + 1] = temp;
	}
}

  • mergeSortArray
    • 版本一 
      static void merge( int32_t a[], int32_t left, int32_t middle, int32_t right, CompareFunc *cmp ) {
	int32_t *tempA = NULL, i = 0, l = left, r = middle + 1;

	if( left < 0 || left > middle || middle > right ) {
		return;
	}
	tempA = malloc( sizeof(*tempA) * (right - left + 1) );
	while( l <= middle && r <= right ) {
		tempA[i++] = cmp( &a[l], &a[r] ) <= 0 ? a[l++] : a[r++];
	}
	while( l <= middle ) {
		tempA[i++] = a[l++];
	}
	while( r <= right ) {
		tempA[i++] = a[r++];
	}
	while( --i >= 0 ) {
		a[left + i] = tempA[i];
	}
	free( tempA );
}

void mergeSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t middle = left + (right - left) / 2;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	if( left >= right ) {
		return;
	}
	mergeSortArray( a, left, middle, cmp );
	mergeSortArray( a, middle + 1, right, cmp );
	merge( a, left, middle, right, cmp );
}
    • 版本二 
      static void merge( int32_t a[], int32_t left, int32_t middle, int32_t right, CompareFunc *cmp ) {
	int32_t *tempA = NULL, i = 0, l = left, r = middle + 1;

	if( left < 0 || left > middle || middle > right ) {
		return;
	}
	tempA = malloc( sizeof(*tempA) * (right - left + 1) );
	while( l <= middle || r <= right ) {
		if( l <= middle && r <= right ) {
			tempA[i++] = cmp( &a[l], &a[r] ) <= 0 ? a[l++] : a[r++];
		} else if( l <= middle ) {
			tempA[i++] = a[l++];
		} else {
			tempA[i++] = a[r++];
		}
	}
	while( --i >= 0 ) {
		a[left + i] = tempA[i];
	}
	free( tempA );
}

void mergeSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t middle = left + (right - left) / 2;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	if( left >= right ) {
		return;
	}
	mergeSortArray( a, left, middle, cmp );
	mergeSortArray( a, middle + 1, right, cmp );
	merge( a, left, middle, right, cmp );
}
    • 版本三 
      static void merge( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp, int32_t tempA[] ) {
	int32_t middle = left + (right - left) / 2;
	int32_t i = 0, l = left, r = middle + 1;

	if( left >= right ) {
		return;
	}
	merge( a, left, middle, cmp, tempA );
	merge( a, middle + 1, right, cmp, tempA );
	while( l <= middle || r <= right ) {
		if( l <= middle && r <= right ) {
			tempA[i++] = cmp( &a[l], &a[r] ) <= 0 ? a[l++] : a[r++];
		} else if( l <= middle ) {
			tempA[i++] = a[l++];
		} else {
			tempA[i++] = a[r++];
		}
	}
	while( --i >= 0 ) {
		a[left + i] = tempA[i];
	}
}

void mergeSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t *tempA = NULL;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	if( left >= right ) {
		return;
	}
	tempA = malloc( sizeof(*tempA) * (right - left + 1) );
	merge( a, left, right, cmp, tempA );
	free( tempA );
}
    • 版本四 
      static void merge( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp, int32_t tempA[] ) {
	int32_t middle = left + (right - left) / 2;
	int32_t i = 0, j = 0;

	if( left >= right ) {
		return;
	}
	merge( a, left, middle, cmp, tempA );
	merge( a, middle + 1, right, cmp, tempA );
	for( j = 0, i = left; i <= middle; ++i ) {
		tempA[j++] = a[i];
	}
	// R.Sedgewick的优化方法, 归并过程中先将后一半逆序再进行归并. 如: [1,4 | 3,7] 变为 [1,4 | 7,3].
	for( i = right; i > middle; --i ) {
		tempA[j++] = a[i];
	}
	for( i = 0, j = right - left; i <= j; ++left ) {
		a[left] = cmp( &tempA[i], &tempA[j] ) <= 0 ? tempA[i++] : tempA[j--];
	}
}

void mergeSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t *tempA = NULL;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	if( left >= right ) {
		return;
	}
	tempA = malloc( sizeof(*tempA) * (right - left + 1) );
	merge( a, left, right, cmp, tempA );
	free( tempA );
}

  • quickSortArray
    • 版本一 
      static void partition( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp, int32_t boundary[2] ) {
	int32_t l = left - 1, c = left, r = right, cmpR = 0;

	while( c < r ) {
		cmpR = cmp( &a[c], &a[right] );
		if( cmpR < 0 ) {
			++l;
			SWAP( a, l, c );
			++c;
		} else if( cmpR == 0 ) {
			++c;
		} else {
			--r;
			SWAP( a, c, r );
		}
	}
	SWAP( a, r, right );
	boundary[0] = l + 1;
	boundary[1] = r;
}

void quickSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t boundary[2] = {-1, -1}, i = 0;

	srand( time( NULL ) );
	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	if( left >= right ) {
		return;
	}
	// left + rand() % (right - left) 取值区间为: [left, right).
	// left + rand() % (right - left + 1) 取值区间为: [left, right].
	i = left + rand() % (right - left);
	SWAP( a, right, i );
	partition( a, left, right, cmp, boundary );
	// boundary[0] 表示等于区间的左闭边界, boundary[1] 表示等于区间的右闭边界.
	quickSortArray( a, left, boundary[0] - 1, cmp );
	quickSortArray( a, boundary[1] + 1, right, cmp );
}
    • 版本二 
      void quickSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, cmpR = 0, l = left - 1, c = left, r = right;

	srand( time( NULL ) );
	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	if( left >= right ) {
		return;
	}
	// left + rand() % (right - left) 取值区间为: [left, right).
	// left + rand() % (right - left + 1) 取值区间为: [left, right].
	i = left + rand() % (right - left);
	SWAP( a, right, i );
	while( c < r ) {
		cmpR = cmp( &a[c], &a[right] );
		if( cmpR < 0 ) {
			++l;
			SWAP( a, c, l );
			++c;
		} else if( cmpR == 0 ) {
			++c;
		} else {
			--r;
			SWAP( a, c, r );
		}
	}
	SWAP( a, right, r );
	quickSortArray( a, left, l, cmp );
	quickSortArray( a, r + 1, right, cmp );
}

  • heapSortArray
    • 版本一 
      static void heapinsert( int32_t heap[], int32_t i, CompareFunc *cmp ) {
	int32_t p = 0;

	for( p = (i - 1) / 2; cmp( &heap[i], &heap[p] ) > 0; p = (i - 1) / 2 ) {
		SWAP( heap, p, i );
		i = p;
	}
}

static void heapify( int32_t heap[], int32_t heapSize, int32_t i, CompareFunc *cmp ) {
	int32_t l = 0, m = 0;

	for( l = i * 2 + 1; l < heapSize; l = i * 2 + 1 ) {
		m = l + 1 < heapSize && cmp( &heap[l + 1], &heap[l] ) > 0 ? l + 1 : l;
		if( cmp( &heap[i], &heap[m] ) > 0 ) {
			break;
		}
		SWAP( heap, m, i );
		i = m;
	}
}

void heapSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, n = right - left + 1;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	if( left >= right ) {
		return;
	}
	for( i = 0; i < n; ++i ) {
		heapinsert( &a[left], i, cmp );
	}
	while( --i > 0 ) {
		SWAP( &a[left], 0, i );
		heapify( &a[left], i, 0, cmp );
	}
}
    • 版本二 
      void heapSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t i = 0, n = right - left + 1;
	int32_t p = 0, index = 0, l = 0, m = 0;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	if( left >= right ) {
		return;
	}
	a += left; // 使a指向 a[left] 元素的首地址.
	for( i = 0; i < n; ++i ) {
		index = i;
		p = (index - 1) / 2;
		for( p = (index - 1) / 2; cmp( &a[index], &a[p] ) > 0; p = (index - 1) / 2 ) {
			SWAP( a, p, index );
			index = p;
		}
	}
	while( --i > 0 ) {
		SWAP( a, 0, i );
		index = 0;
		for( l = index * 2 + 1; l < i; l = index * 2 + 1 ) {
			m = l + 1 < i && cmp( &a[l + 1], &a[l] ) > 0 ? l + 1 : l;
			if( cmp( &a[index], &a[m] ) > 0 ) {
				break;
			}
			SWAP( a, index, m );
			index = m;
		}
	}
}

  • countSortArray 
    void countSortArray( int32_t a[], int32_t left, int32_t right, CompareFunc *cmp ) {
	int32_t *count = NULL, i = 0, j = 0, min = INT32_MAX, max = INT32_MIN;

	ERROR_EXIT( !a || left < 0 || !cmp, NULL );
	for( i = left; i <= right; ++i ) {
		min = MIN( min, a[i] );
		max = MAX( max, a[i] );
	}
	if( min == max ) {
		return;
	}
	count = calloc( sizeof(*count), (max - min + 1) );
	for( i = left; i <= right; ++i ) {
		++count[a[i] - min]; 
	}
	if( cmp( &min, &max ) <= 0 ) {
		for( i = min; i <= max; ++i ) {
			for( j = count[i - min]; j > 0; --j ) {
				a[left++] = i;
			}
		}
	} else {
		for( i = max; i >= min; --i ) {
			for( j = count[i - min]; j > 0; --j ) {
				a[left++] = i;
			}
		}
	}
	free( count );
}

  • radixSortArray

sortArrayTest.c 
实现对数器.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include "sortArray.h"


#define MAX( a, b ) ((a) > (b) ? (a) : (b))


// 功能: 对数组的某一区间内的元素值进行随机化.
// 参数: a(数组首地址), left(左闭区间), right(右闭区间), v(最大随机值).
// 返回: 无.
// 注意: 当v是正数/负数/零时,随机值的区间分别为[-v, v]/[]/[].
static void randomArray( int32_t a[], int32_t left, int32_t right, int32_t v ) {
	v -= v != INT32_MAX ? 0 : 1;
	while( left <= right ) {
		a[left++] = rand() % (v + 1) - rand() % (v + 1);
	}
}

// 功能: 将源数组的某一区间内的元素值拷贝至目的数组中.
// 参数: a(源数组首地址), left(左闭区间), right(右闭区间), b(目的数组首地址).
// 返回: 无.
// 注意: 无.
static void cloneArray( const int32_t a[], int32_t left, int32_t right, int32_t b[] ) {
	while( left <= right ) {
		b[left] = a[left];
		++left;
	}
}

// 功能: 将数组的某一区间内的元素值送入到文件流中.
// 参数: a(数组首地址), left(左闭区间), right(右闭区间), fp(文件流指针).
// 返回: 无.
// 注意: 无.
static void printArray( const int32_t a[], int32_t left, int32_t right, FILE *fp ) {
	fprintf( fp, "[" );
	while( left <= right ) {
		fprintf( fp, "%5d%s", a[left], left != right ? ", " : "" );
		++left;
	}
	fprintf( fp, "]
" );
}

// 功能: 数据比较.
// 参数: a(数据1), b(数据2).
// 返回: a<b返回负数, a>b返回正数, 否则返回0.
// 注意: 无.
static int cmp( const void *a, const void *b ) {
	#if 1
	return *(int32_t *) a - *(int32_t *) b;
	#else
	return *(int32_t *) b - *(int32_t *) a;
	#endif
}

// 功能: 绝对正确的方法.
// 参数: a(数组首地址), left(左闭区间), right(右闭区间).
// 返回: 无.
// 注意: 使用稳定的库函数方法 或 非常笨的方法(如暴力循环,暴力递归搜索).
static void correct( int32_t a[], int32_t left, int32_t right ) {
	qsort( &a[left], right - left + 1, sizeof(*a), cmp );
}

// 功能: 待测试的方法.
// 参数: a(数组首地址), left(左闭区间), right(右闭区间).
// 返回: 无.
// 注意: 使用技巧性的高效的正确性未知的方法.
static void test( int32_t a[], int32_t left, int32_t right ) {
	selectSortArray( a, left, right, cmp );
	//bubbleSortArray( a, left, right, cmp );
	//insertSortArray( a, left, right, cmp );
	//mergeSortArray( a, left, right, cmp );
	//quickSortArray( a, left, right, cmp );
	//heapSortArray( a, left, right, cmp );
	//countSortArray( a, left, right, cmp );
}

// 功能: 比较两数组的同区间内的元素是否全部相等.
// 参数: a(数组首地址), b(数组首地址), left(左闭区间), right(右闭区间).
// 返回: 区间内的元素全部相等返回1, 否则返回0.
// 注意: 无.
static int equal( const int32_t a[], const int32_t b[], int32_t left, int32_t right ) {
	while( left <= right ) {
		if( a[left] != b[left] ) {
			return 0;
		}
		++left;
	}

	return 1;
}

int main( int argc, char *argv[] ) {
	const int32_t times = 7654321; // 测试的总测试.
	const int32_t maxSize = 21;    // 随机的最大长度.
	int32_t size = 0, left = 0, right = 0;
	int32_t *a = NULL, *t = NULL, *c = NULL;
	int32_t i = 0;

	srand( time( NULL ) );
	a = malloc( sizeof(*a) * maxSize );
	c = malloc( sizeof(*c) * maxSize );
	t = malloc( sizeof(*t) * maxSize );

	for( i = 0; i < times; ++i ) {
		size = rand() % (maxSize + 1); // 随机化数组长度.

		randomArray( a, 0, size - 1, 321 );
		cloneArray( a, 0, size - 1, c );
		cloneArray( a, 0, size - 1, t );

		left = 0;
		right = size - 1;

		#if 1 // 随机化排序区间.
		left = rand() % MAX( size, 1 );
		do {
			right = rand() % MAX( size, 1 );
		} while( right < left );
		#endif

		correct( c, left, right ); // 绝对正确的方法.
		test( t, left, right );    // 待测试的方法.
		if( !equal( c, t, 0, size - 1 ) ) {
			fprintf( stderr, "source  :" );
			printArray( a, 0, size - 1, stderr );
			fprintf( stderr, "correct :" );
			printArray( c, 0, size - 1, stderr );
			fprintf( stderr, "test    :" );
			printArray( t, 0, size - 1, stderr );
			fprintf( stderr, " 本次测试不通过!
a" );
			exit( EXIT_FAILURE );
		}
	}

	free( t );
	free( c );
	free( a );

	printf( "总共 %d 次测试且全部通过!
", times );

	return EXIT_SUCCESS;
}

sortArrayTest.sh 
# !/bin/bash

for(( i = 1; i <= 21; ++i )) do
	printf "%02d" ${i}
	echo -n ____________
	./sortArrayTest
done



【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/hujunxiang98/p/12878521.html