// 快速排序.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "stdlib.h"
#include "stdio.h"
#define MAXSIZE 10
typedef struct {
int keyWord;
int otherWord;
}Elemtype;
typedef struct
{
Elemtype * data;
int length;
}List,*PList;
void initList(PList L)
{
L->data = (Elemtype *)malloc(sizeof(Elemtype)*MAXSIZE);
L->length = 0;
}
void createList(PList L)
{
initList(L);
printf("input the total of your nums,but attention,the tips can't beyond %d\n",MAXSIZE);
scanf_s("%d",&L->length);
for (int i = 1; i <= L->length; i++)
{
scanf_s("%d",&L->data[i].keyWord);
}
}
int Partition(PList L,int low,int high)
{
//49 38 65 97 76 13 27 *49 <- 进行排序
L->data[0].keyWord = L->data[low].keyWord; //将第一个元素作为枢轴点保存
int pivotkey = L->data[low].keyWord;
while (low<high) //从最后一个元素开始比较
{
if(L->data[high].keyWord>=pivotkey) high--;
//or refill the nums of low with the nums of high
L->data[low].keyWord = L->data[high].keyWord;
if(L->data[low].keyWord<=pivotkey) low++;
L->data[high].keyWord = L->data[low].keyWord;
}
//break shows low==high
//refill the low position with L->data[0].keyWord
L->data[low].keyWord = L->data[0].keyWord;
return low;
}
void QSort(PList L,int low ,int high) //Quickly Sort..
{
if(low<high) //lenth are more than 1
{
int pivotkey = Partition(L,low,high);
QSort(L,low,pivotkey-1);
QSort(L,pivotkey+1,high);
}
}
void QucikSort(PList L)
{
QSort(L,1,L->length);
}
int _tmain(int argc, _TCHAR* argv[])
{
List L;
createList(&L);
QucikSort(&L);
for (int i = 1; i <= L.length; i++)
{
printf("%d\t",L.data[i].keyWord);
}
return 0;
}