# 数据结构(C语言版)第七章:排序 原

fzyz_sb

PS:对排序比较感兴趣,所以就先学习第七章排序,第六章图就先放着.

7.1 查找与表验证

1. 折半查找

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

int binsearch( int list[], int searchNum, int n );
int count = 0;
int main( void )
{
int list[ 1000 ];
int i = 0;
for ( i = 0; i < 1000; i++ ){
list[ i ] = i;
}

binsearch( list, 65, 1000 );

printf("%d\n", count );

return 0;
}

int binsearch( int list[], int searchNum, int n )
{
int left = 0;
int right = n - 1;
int middle;
while ( left <= right ){
count++;
middle = ( left + right ) / 2;
if ( list[ middle ] == searchNum ){
return middle;
}
else if ( list[ middle ] < searchNum ){
left = middle + 1;
}
else{
right = middle - 1;
}
}

return -1;
}

2. 表验证

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

#define MAX_SIZE 100

void verify( int list1[], int list2[], int len1, int len2 );
int search( int list[], int len, int searchNum );

int main( void )
{
int list1[] = { 1, 5, 2, 8, 3, 9, 4, 10, 7, 6 };
int list2[] = { 10, 2, 10, 4, 9, 11 };
int len1 = sizeof( list1 ) / sizeof( *list1 );
int len2 = sizeof( list2 ) / sizeof( *list2 );

verify( list1, list2, len1, len2 );

return 0;
}

void verify( int list1[], int list2[], int len1, int len2 )
{
int mark[ MAX_SIZE ];
int i = 0;
int isFind = 0;
memset( mark, 0, sizeof( int ) * len2 );
for ( i = 0; i < len2; i++ ){
if ( !search( list1, len1, list2[ i ] ) ){
mark[ i ] = 1;
}
}

for ( i = 0; i < len2; i++ ){
if ( mark[ i ] ){
printf("%d ", list2[ i ] );
isFind = 1;
}
}

if ( isFind ){
printf(" not in list1\n");
}
else{
printf("list2 in list1\n");
}
}

int search( int list[], int len, int searchNum )
{
int i = 0;
for ( i = 0; i < len; i++ ){
if ( searchNum == list[ i ] ){
return 1;
}
}

return 0;
}

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

#define MAX_SIZE 100

void verify( int list1[], int list2[], int len1, int len2 );
void sort( int list[], int len );
void swap( int *pa, int *pb );

int main( void )
{
int list1[] = { 1, 5, 2, 8, 3, 9, 4, 10, 7, 6 };
int list2[] = { 9, 3, 5, 1, 11, 14, 12, 2 };
int len1 = sizeof( list1 ) / sizeof( *list1 );
int len2 = sizeof( list2 ) / sizeof( *list2 );

verify( list1, list2, len1, len2 );

return 0;
}

void verify( int list1[], int list2[], int len1, int len2 )
{
int i = 0;
int j = 0;
sort( list1, len1 );
sort( list2, len2 );
while ( i < len1 && j < len2 ){
if ( list1[ i ] < list2[ j ] ){
printf("%d is not in list 2\n", list1[ i ] );
i++;
}
else if ( list1[ i ] == list2[ j ] ){
i++;
j++;
}
else{
printf("%d is not in list 1 \n", list2[ j ] );
j++;
}
}

for ( ; i < len1; i++ ){
printf("%d is not in list 2\n", list1[ i ] );
}
for ( ; j < len2; j++ ){
printf("%d is not in list 1\n", list2[ j ] );
}
}

/*

*/
void sort( int list[], int len )
{
int i = 0;
int j = 0;
for ( i = 0; i < len - 1; i++ ){
for ( j = i + 1; j < len; j++ ){
if ( list[ i ] > list[ j ] ){
swap( &list[ i ], &list[ j ] );
}
}
}
}

void swap( int *pa, int *pb )
{
int temp = *pa;
*pa = *pb;
*pb = temp;
}

7.3 插入排序

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

void insertSort( int list[], int len );
void show( int list[], int len );
int main( void )
{
int list1[] = { 1, 5, 2, 8, 3, 9, 4, 10, 7, 6 };
int len = sizeof( list1 ) / sizeof( *list1 );
insertSort( list1, len );

show( list1, len );

return 0;
}

void insertSort( int list[], int len )
{
int i = 0;
int j = 0;
int next = 0;
for ( i = 1; i < len; i++ ){
next = list[ i ];
for ( j = i - 1; j >= 0 && next < list[ j ]; j-- ){
list[ j+ 1 ] = list[ j ];
}
list[ j + 1 ] = next;
}
}

void show( int list[], int len )
{
int i = 0;
for ( i = 0; i < len; i++ ){
printf("%d ", list[ i ] );
}
}

7.4 快速排序

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

void quicksort( int list[], int left, int right );
void show( int list[], int len );
void swap( int *pa, int *pb );
int main( void )
{
int list1[] = { 26, 5, 37, 1, 61, 11, 59, 15, 48, 19 };
int len = sizeof( list1 ) / sizeof( *list1 );
quicksort( list1, 0, len - 1 );

printf("\nthe sort list is:\n");
show( list1, len );

return 0;
}

void quicksort( int list[], int left, int right )
{
int pivot;
int i;
int j;
if ( left < right ){
i = left;
j = right + 1;
pivot = list[ left ];
do{
do{
i++;
}while ( list[ i ] < pivot );
do{
j--;
}while ( list[ j ] > pivot );
if ( i < j ){
swap( &list[ i ], &list[ j ] );
}
}while ( i < j );
swap( &list[ left ], &list[ j ] );
show( &list[ 0 ], 10 );
quicksort( list, left, j - 1 );
quicksort( list, j + 1, right );
}
}

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

void swap( int *pa, int *pb )
{
int temp = *pa;
*pa = *pb;
*pb = temp;
}

void quicksort( int list[], int left, int right )
{
int pivot;
int i;
int j;
if ( left < right ){
i = left;
j = right + 1;
pivot = list[ left ];
do{
do{
i++;
}while ( list[ i ] < pivot );
do{
j--;
}while ( list[ j ] > pivot );
if ( i < j ){
swap( &list[ i ], &list[ j ] );
}
show( &list[ 0 ], 10 );
}while ( i < j );
swap( &list[ left ], &list[ j ] );
show( &list[ 0 ], 10 );
quicksort( list, left, j - 1 );
quicksort( list, j + 1, right );
}
}

quicksort( list, left, j - 1 );
quicksort( list, j + 1, right );

7.6 归并排序

7.6.1 归并

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

int *merge( int list[], int start, int middle, int end )
{
int *sorted = ( int * )malloc( sizeof( int ) * ( end - start + 1 ) );
int *temp = sorted;
int i = 0;
int j = middle + 1;
while ( i <= middle && j <= end ){
if ( list[ i ] <= list[ j ] ){
*sorted++ = list[ i++ ];
}
else{
*sorted++ = list[ j++ ];
}
}
while ( i <= middle ){
*sorted++ = list[ i++ ];
}
while ( j <= end ){
*sorted++ = list[ j++ ];
}
return temp;
}

int main( void )
{
int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
int *parr = NULL;
int i = 0;
parr = merge( arr, 0, 4, 9 );

for ( i = 0; i < 10; i++ ){
printf("%d ", parr[ i ] );
}

return 0;
}

1. 对于数组的操作,通常是需要新建一个临时的内存来存放操作好的数据的,这样不会陷入指针的危机中(因为数组本身就是指针,你通过操作地址可能会影响原本的值).

2. 数组指针是int *就可以了.这样更方便的操作.

3. 如果这道题改为改变list的话,那么将很难操作而且很容易出错.因为list的地址不能被改变,你除非一次次的赋值才可以.

7.6.2 归并排序的迭代算法

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

#define MAX_SIZE 20
void merge( int list[], int sorted[], int i, int m, int n )
{
int j, k, t;
j = m + 1;
k = i;
while ( i <= m && j <= n ){
if ( list[ i ] <= list[ j ] ){
sorted[ k++ ] = list[ i++ ];
}
else{
sorted[ k++ ] = list[ j++ ];
}
}
if ( i > m ){
for ( t = j; t <= n; t++ ){
sorted[ k + t - j ] = list[ t ];
}
}
else{
for ( t = i; t <= m; t++ ){
sorted[ k + t - i ] = list[ t ];
}
}
}

void merge_pass( int list[], int sorted[], int n, int length )
{
int i, j;
for ( i = 0; i <= n - 2 * length; i += 2 * length ){
merge( list, sorted, i, i + length - 1, i + 2 * length - 1 );
}
if ( i + length < n ){
merge( list, sorted, i, i + length - 1, n - 1 );
}
else{
for ( j = i; j < n; j++ ){
sorted[ j ] = list[ j ];
}
}
}

void merge_sort( int list[], int n )
{
int length = 1;
int extra[ MAX_SIZE ];

while ( length < n ){
merge_pass( list, extra, n, length );
length *= 2;
merge_pass( extra, list, n, length );
length *= 2;
}
}

int main( void )
{
int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
int i = 0;
merge_sort( arr, 10 );

for ( i = 0; i < 10; i++ ){
printf("%d ", arr[ i ] );
}
printf("\n");

return 0;
}

void merge_sort( int list[], int n )
{
int length = 1;
int extra[ MAX_SIZE ];

while ( length < n ){
printf("\nOK-->\n");
merge_pass( list, extra, n, length );
printf("list: ");
show( &list[ 0 ], 10 );
printf("extra: ");
show( &extra[ 0 ], 10 );
length *= 2;
merge_pass( extra, list, n, length );
printf("list: ");
show( &list[ 0 ], 10 );
length *= 2;
}
}

7.6.3 归并排序的递归算法

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

#define MAX_SIZE 20

void merge( int list[], int lower, int middle, int upper )
{
int *sorted = ( int * )malloc( sizeof( int ) * ( upper - lower + 1 ) );
int *start = sorted;
int i = lower;
int j = middle + 1;
while ( i <= middle && j <= upper ){
if ( list[ i ] < list[ j ] ){
*sorted++ = list[ i++ ];
}
else{
*sorted++ = list[ j++ ];
}
}
while ( i <= middle ){
*sorted++ = list[ i++ ];
}
while ( j <= upper ){
*sorted++ = list[ j++ ];
}
for ( i = lower; i <= upper; i++ ){
list[ i ] = *start++;
}
}

void rmerge( int list[], int lower, int upper )
{
int middle;
if ( lower < upper ){
middle = ( lower + upper ) / 2;
rmerge( list, lower, middle );
rmerge( list, middle + 1, upper );
merge( list, lower, middle, upper );
}
}

int main( void )
{
int arr[] = { 12, 43, 2, 98, 14, 21, 66, 3, 111, 9 };
int i = 0;
rmerge( arr, 0, 9 );

for ( i = 0; i < 10; i++ ){
printf("%d ", arr[ i ] );
}
printf("\n");

return 0;
}

void merge( int list[], int lower, int middle, int upper )

### fzyz_sb

2017/11/07
0
0
C语言书籍资料汇总

BjarneCpp
2017/11/06
0
0
Linux C编程如何使用联机帮助来解决编程问题?

1.背景 多次学习C语言一直无法踏入C语言的大门，每次都是在学习C语言中的那些系统调用库函数等望而却只，linux下的系统调用需要我们去记忆一些没有规律的结构体和一些大写的宏定义并且还有一...

Jeff_Linux
2014/07/06
0
0

2013/01/06
262
0

modernizr
2014/05/22
28.1K
13

《Netkiller Java 手札》· 二进制文件操作大全

netkiller-
13分钟前
0
0
Fiddler Debugger post请求

20分钟前
1
0

ThinkSNS账号
22分钟前
0
0
Android 自定义构建类型 BuildType

23分钟前
1
0

26分钟前
0
0