데이터 구조 정렬 알고리즘 의 빠 른 정렬 (c 언어 구현)

빠 른 배열 의 원 리 는 한 번 의 정렬 을 통 해 대기 기록 을 독립 된 두 부분 으로 나 누 는 것 이다. 그 중에서 일부 기록 의 키 워드 는 모두 다른 부분 에 기 록 된 키워드 보다 작 으 면 이 두 부분 에 대한 기록 을 계속 정렬 하여 전체 서열 의 질 서 를 달성 할 수 있다.그 중에서 특정한 관건 적 인 함 수 를 재 귀적 으로 호출 하 는 방법 으로 이런 기능 을 실현 할 수 있다.
분할 방법 은 하나의 중심 축 을 선택 하여 모든 키 워드 를 작은 기록 보다 그 위치 에 배치 하기 전에 모든 키 워드 를 큰 기록 보다 그 위치 에 배치 하 는 것 이다.
구체 적 인 방법 은 서열 의 양 끝 을 취하 고 한 끝 에 있 는 표지 나 지침 은 low 이 며 다른 한 끝 에 있 는 표지 나 지침 은 high 이다.하 이 가 가리 키 는 원소 의 값 을 추축 과 비교 하고 추축 의 값 보다 크 면 하 이 를 어느 위치 로 옮 기 고 그 값 이 추축 의 값 보다 작 으 면 로 우 에 게 부여 하 는 위치 (추축 기록 보다 작은 것 을 낮은 곳 으로 옮 기 는 것).그 다음 에 low 가 가리 키 는 위치 부터 뒤로 검색 하면 검색 과정 은 하 이 엔 드 와 같 습 니 다. 다만 중추 보다 작 으 면 low 를 계속 뒤로 이동 시 키 고 특정한 위치 로 이동 할 때 까지 그 값 이 중추 의 값 보다 크 면 하 이 에 게 부여 합 니 다 (중추 보다 큰 것 을 고급 으로 기록 합 니 다).low = high 가 멈 출 때 까지 반복 합 니 다.되 돌아 오 는 pivotloc 값 은 마지막 low 값 입 니 다.
선행 코드

#include "stdafx.h"    
#include "stdio.h"    
#include "malloc.h"    
#include     
#include     

#define OK 1  
#define ERROR 0  
typedef int Status;

typedef struct {
	int *Data;
	int length;
}SqList;

Status InitSqList(SqList *S) {
	int n;
	printf("           ：
");
	scanf_s("%d", &n);
	getchar();//         
	S->length = n;
	S->Data = (int*)malloc((n + 1)*sizeof(int));
	if (!S->Data)return ERROR;
	S->Data[0] = 0;//      pivotkey  
	for (int i = 1; i <= n; i++) {
		printf(" %d   :", i);
		scanf_s("%d", &S->Data[i]);
		getchar();//         
	}
	return OK;
}

int Partition(SqList *S, int low, int high) {
	int pivotkey = S->Data[low];
	S->Data[0] = S->Data[low];// S->Data[0]       S->Data[low]  ， pivotkey，         ，              
	while (low < high) {
		while (low < high&&S->Data[high] >= pivotkey)
			high--;// high     pivotkey       
		S->Data[low] = S->Data[high];//    pivotkey           
		while (low < high&&S->Data[low] <= pivotkey)
			low++;// low     pivotkey       
		S->Data[high] = S->Data[low];//    pivotkey           
	}
	S->Data[low] = S->Data[0];//           
	return low;//   low=high=    pivotkey
}

void QSort(SqList *S, int low, int high) {
	int pivotloc;
	if (low < high) {
		pivotloc = Partition(S, low, high);//    pivot   loc，           ，           
		QSort(S, low, pivotloc - 1);
		QSort(S, pivotloc + 1, high);
	}
}

void QuickSort(SqList *S) {
	QSort(S, 1, S->length);
}

int main()
{
	SqList S;
	InitSqList(&S);
	QuickSort(&S);
	printf("
");
	for (int i = 1; i <= S.length; i++) {
		printf(" %d   \t%d
", i, S.Data[i]);
	}
	system("pause");
	return 0;
}

운행 은 성공 적 이다.