/********************************************************************************************************************/
/**/
/*功能名:快速排序英名 : Sort_Quick.c*/
/**/
/* 概要:快速排序*/
/**/
/*構成設計:刘　增林2015.12.10*/
/*詳細設計:刘　增林2015.12.10*/
/*メーキング:刘　增林2015.12.10*/
/*All Rights Reserved, Copyright (c) Transtron Inc. 2015*/
/********************************************************************************************************************/
/*改版履歴:ＮＡＭＥ9999/99/99ＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸ*/
/*:ＮＡＭＥ9999/99/99ＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸＸ*/
/********************************************************************************************************************/
/********************************************************************************************************************/
/*１．インクルードファイル区( Include File )*/
/********************************************************************************************************************/
#include <stdio.h>
#include <stdlib.h>
/********************************************************************************************************************/
/*３．ローカルマクロ区( Local Macros )*/
/********************************************************************************************************************/
/********************************************************************************************************************/
/*４．グローバル変数区( Global Table )*/
/********************************************************************************************************************/
/********************************************************************************************************************/
/*５．ローカル変数区( Local Variables )Static*/
/********************************************************************************************************************/
/********************************************************************************************************************/
/*６．ローカルモジュール(プロトタイプ宣言)区( Local Function Prototypes )Static*/
/********************************************************************************************************************/
static voidSort_Swap( WORD *swap_left, WORD *swap_right );/*交换左参数和右参数的值*/
static voidSort_QuickSort( WORD list[], WORD left, WORD right);/*实现快速排序的主要功能*/
static voidSort_PrintList( WORD *list, WORD length );/*输出list数组的值*/
/********************************************************************************************************************/
/**/
/*モジュール名:交换数字英名 : Sort_Swap*/
/**/
/*概要:把函数的两个参数交换*/
/**/
/*入力パラメータ:WORD *swap_left交换之前的左变量*/
/*WORD *swap_right交换之前的右变量*/
/**/
/*出力パラメータ:WORD *swap_left交换之后的左变量*/
/*WORD *swap_right交换之后的右变量*/
/**/
/*復帰値:無し*/
/**/
/********************************************************************************************************************/
voidSort_Swap( WORD *swap_left, WORD *swap_right )
{
WORD temp;/*定义中间变量*/
/****************************************************************************************************************/
/*１．指针检查*/
/****************************************************************************************************************/
if(!swap_left||!swap_right)/*任一指针为空则调到exit位置*/
{
goto exit1;
}
/****************************************************************************************************************/
/*2．通过中间变量进行交换*/
/****************************************************************************************************************/
temp = *swap_left;
*swap_left = *swap_right;
*swap_right = temp;
/****************************************************************************************************************/
/*3．指针为空的跳出位置*/
/****************************************************************************************************************/
exit1：;
/****************************************************************************************************************/
/*９９．復帰*/
/****************************************************************************************************************/
return;
}
/********************************************************************************************************************/
/**/
/*モジュール名:快速排序英名 : Sort_QuickSort*/
/**/
/*概要:快速排序*/
/**/
/*入力パラメータ:WORD *list待排序数组*/
/*WORD left待排序数组左侧起始位置*/
/*WORD right待排序数组右侧终止位置*/
/*WORD length数组长度*/
/**/
/*出力パラメータ:WORD *list排序之后的数组*/
/**/
/*復帰値:無し*/
/**/
/********************************************************************************************************************/
voidSort_QuickSort( WORD *list, WORD left, WORD right， WORD length)
{
WORD key;/*快速排序的基准值*/
WORD temp_left;
WORD temp_right;
WORD mid;
/****************************************************************************************************************/
/*１．指针检查*/
/****************************************************************************************************************/
if(!list)/*若指针为空，则跳转到exit位置*/
{
goto exit2;
}
/****************************************************************************************************************/
/*2．数组下标值left在right的左侧时进行排序，否则返回*/
/****************************************************************************************************************/
if( left < right)
{
/************************************************************************************************************/
/*2．1 快速排序核心程序*/
/************************************************************************************************************/
mid = ( left + right ) / 2;/*取得左右下标的中间值*/
Swap( &list[left], &list[mid] );/*把待排数组的左值和中间值交换*/
key = list[left];/*把此时的左值作为基准值*/
temp_left = left + 1;/*取得基准值相邻右侧的下表作为temp_left*/
temp_right = right;/*取得待排数组最右的下表作为temp_right*/
while( temp_left <= temp_right )/*当下标不相遇时循环*/
{
while( ( temp_left <= right ) && (list[temp_left] <= key ) )
/*从左侧开始，值小于基准值则向右跳转到下一个值*/
{
temp_left++;
}
while((temp_right >= left) && (list[temp_right] > key))
/*从右侧开始，值大于基准值则向左跳转到下一个值*/
{
temp_right--;
}
if( temp_left < temp_right)/*符合上述条件的两个值分别在key值左右*/
{
Swap( &list[temp_left], &list[temp_right] );
}
}
Sort_Swap( &list[left], &list[temp_right] );/*交换两个元素的位置*/
Sort_QuickSort( list, left, temp_right-1 );/*递归地对基准值左侧的数据序列进行排序*/
Sort_QuickSort( list, temp_right+1, right );/*递归地对基准值右侧的数据序列进行排序*/
}
/****************************************************************************************************************/
/*3．指针为空的跳出位置*/
/****************************************************************************************************************/
exit2：;
/****************************************************************************************************************/
/*９９．復帰*/
/****************************************************************************************************************/
return;
}
/********************************************************************************************************************/
/**/
/*モジュール名:显示数组英名 : Sort_PrintList*/
/**/
/*概要:显示数组*/
/**/
/*入力パラメータ:WORD list待输出数组*/
/*WORD legth数组长度*/
/**/
/*出力パラメータ:無し*/
/**/
/*復帰値:無し*/
/**/
/********************************************************************************************************************/
voidSort_PrintList( WORD *list, WORD length )
{
/****************************************************************************************************************/
/*１．循环输出list数组*/
/****************************************************************************************************************/
for( WORD count = 0; count < length; count++ )
{
printf( "%d\t", list[count] );
}
/****************************************************************************************************************/
/*９９．復帰*/
/****************************************************************************************************************/
return;
}
/********************************************************************************************************************/
/**/
/*モジュール名:主函数英名 : main*/
/**/
/*概要:主函数*/
/**/
/*入力パラメータ:無し*/
/**/
/*出力パラメータ:無し*/
/**/
/*復帰値:無し*/
/**/
/********************************************************************************************************************/
voidmain( void )
{
const WORD max = 10;
WORD list[max];
/****************************************************************************************************************/
/*1．填充list数组*/
/****************************************************************************************************************/
for(WORD count = 0; count < max; count++ )/*产生小于100的填充数组的随机数*/
{
list[count] = rand()%100;
}
/****************************************************************************************************************/
/*2．打印出带排序数组*/
/****************************************************************************************************************/
printf( "排序之前的序列:" );
Sort_PrintList( list, max );/*调用Sort_PrintList函数打印*/
/****************************************************************************************************************/
/*3．对数组进行排序*/
/****************************************************************************************************************/
Sort_QuickSort( list, 0, max-1 );
/****************************************************************************************************************/
/*4．打印出已排序数组*/
/****************************************************************************************************************/
printf( "排序之后的序列:" );
Sort_PrintList( list, max );/*调用Sort_PrintList函数打印*/
/****************************************************************************************************************/
/*９９．復帰*/
/****************************************************************************************************************/
return;
}