빠 른 정렬 알고리즘 다양한 언어 구현
n 항목
Θ(
n log
n) 차 비교.그러나 최 악의 성능 에 서 는 필요 하 다.
Θ(
n
2) 차 비교.일반적으로 빠 른 정렬 은 실제로 다른 것 보다 뚜렷 하 다.
Θ(
n log
n) 알고리즘 이 더 빠 릅 니 다. 내부 순환 (inner loop) 은 대부분의 구조 에서 효율 적 으로 이 루어 질 수 있 고 대부분의 실제 세계 의 데 이 터 는 디자인 의 선택 을 결정 하여 필요 한 시간의 2 차 항목 의 가능성 을 줄 일 수 있 기 때 문 입 니 다.
빠 른 정렬 은 두 갈래 찾기 트 리 (두 갈래 찾기 트 리) 의 공간 최적화 버 전 입 니 다.항목 을 명확 한 트 리 에 순서대로 삽입 하지 않 고 빠 른 정렬 로 구성 합 니 다.이 두 알고리즘 은 완전히 같은 비교 횟수 를 만 들 었 지만 순서 가 다르다.
빠 른 정렬 의 가장 직접적인 경쟁 자 는 쌓 기 정렬 (Heapsort) 이다.쌓 기 정렬 은 보통 빠 른 정렬 보다 약간 느 리 지만 최 악의 경우 에는 항상 O (n) 입 니 다. log n)。빠 른 정렬 은 항상 빠 르 고 introsort 변화 버 전 을 제외 하고 최 악의 상황 성능 을 가 질 수 있 는 기회 입 니 다.쌓 기 정렬 이 필요 하 다 는 것 을 미리 알 았 다 면, 직접 쌓 기 정렬 을 사용 하 는 것 이 introsort 를 기다 리 는 것 보다 더 빠 릅 니 다.쌓 기 정렬 도 중요 한 특징 을 가지 고 있 습 니 다. 고정 적 인 추가 공간 (쌓 기 정렬 은 제자리 정렬) 만 사용 하고 가장 빠 른 정렬 변화 버 전 이라도 필요 합 니 다.Θ(log n) 의 공간.그러나 쌓 기 정렬 은 효율 적 인 랜 덤 액세스 가 필요 하 다.
빠 른 정렬 도 병합 정렬 (Mergesort) 과 경쟁 합 니 다. 이것 은 다른 재 귀 정렬 알고리즘 이지 만 나 쁜 경우 O (n) 가 있 습 니 다. log n) 운행 시간의 장점.빠 른 정렬 이나 정렬 이 아 닌 병합 정렬 은 안정 적 인 정렬 이 며 링크 (linked list) 와 느 린 속도 로 미디어 에 저장 되 어 플 로 피 디스크 저장 이나 네트워크 연결 에 저 장 된 매우 큰 수열 처럼 쉽게 사용 할 수 있 습 니 다.빠 른 정렬 은 직렬 에 다시 쓸 수 있 지만 무 작위 액세스 가 불가능 해 기준 선택 이 떨 어 지 는 경우 가 많 습 니 다.정렬 의 주요 단점 은 가장 좋 은 상황 에서 오 메 가 (n) 의 추가 공간 이 필요 하 다 는 것 이다.
이 를 통 해 우 리 는 여러 언어 에서 빠 른 정렬 을 보 여 줍 니 다.우 리 는 여기에서 가장 보편적 이거 나 독특한 것 만 보 여 준다.다른 실현 에 대해 서 는 빠 른 정렬 실현 항목 을 참조 하 십시오.
주 항목: 빠 른 정렬 실현
[편집] C
정수 배열 을 정렬 하 다.
void swap(int *a, int *b)
{
int t=*a; *a=*b; *b=t;
}
void quicksort(int arr[],int beg,int end)
{
if (end >= beg + 1)
{
int piv = arr[beg], k = beg + 1, r = end;
while (k < r)
{
if (arr[k] < piv)
k++;
else
swap(&arr[k], &arr[r--]);
}
if (arr[k] < piv){
r++;
swap(&arr[k],&arr[beg]);
quicksort(arr, beg, k);
quicksort(arr, r, end);
}else {
if (end - beg == 1)
return;
swap(&arr[--k],&arr[beg]);
quicksort(arr, beg, k);
quicksort(arr, r, end);
}
}
}
다른 버 전
void swap(int *a, int *b)
{
int t=*a; *a=*b; *b=t;
}
void qsort(int arr[],int l,int r)
{
int i = l;
int j = r;
int key = arr[(i+j)/2];
while(i < j)
{
for(;(i < r)&&(arr[i] < key);i++);
for(;(j > l)&&(arr[j] > key);j--);
if (i <= j)
{
if ( i != j)
{
swap(&arr[i],&arr[j]);
}
i++;
j--;
}
}
if (i < r)
qsort(arr,i,r);
if (j > l)
qsort(arr,l,j);
}
세 번 째 버 전.
/************************************************************************/
/* ， ， swap ，longrenle*/
/************************************************************************/
void quickSort(int data[], int left, int right)
{
int temp = data[left];
int ptr = left;
int i = left + 1, j = right;
if(data[i] <= temp)
{
data[ptr] = data[i];
ptr = i;
}
while(i!=j)
{
if(data[j] >= temp)
{
j--;
}
else
{
data[ptr] = data[j];
ptr = j;
while(data[i] <= temp && i != j)
{
i++;
}
data[ptr] = data[i];
ptr = i;
}
}
data[ptr] = temp;
if(left < ptr - 1)
quickSort(data, left, ptr - 1);
if(ptr + 1 < right)
quickSort(data, ptr + 1, right);
}
[편집] C + +
이것 은 표준 모드 라 이브 러 리 (STL) 를 사용 하 는 범 형식 빠 른 정렬 버 전 입 니 다.
#include [편집] Java
import java.util.Comparator;
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private static void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private static <E> int partition(E[] array, int begin, int end, Comparator super E> cmp) {
int index = begin + RND.nextInt(end - begin + 1);
E pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private static <E> void qsort(E[] array, int begin, int end, Comparator super E> cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public static <E> void sort(E[] array, Comparator super E> cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}
[편집] Perl
sub qsort {
return () unless @_;
(qsort(grep { $_ < $_[0] } @_[1..$#_]), $_[0],
qsort(grep { $_ >= $_[0] } @_[1..$#_]));
}
[편집] 파 이 썬
def qsort(L):
if not L: return []
return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \
qsort([x for x in L[1:] if x>=L[0]])
[편집] Joy
DEFINE sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .
[편집] PHP
function quicksort($seq) {
if (count($seq) > 1) {
$k = $seq[0];
$x = array();
$y = array();
for ($i=1; $i<count($seq); $i++) {
if ($seq[$i] <= $k) {
$x[] = $seq[$i];
} else {
$y[] = $seq[$i];
}
}
$x = quicksort($x);
$y = quicksort($y);
return array_merge($x, array($k), $y);
} else {
return $seq;
}
}
[편집] Haskell
sort :: (Ord a) => [a] -> [a]
sort [] = []
sort (pivot:rest) = sort [y | y rest, y < pivot]
++ [pivot] ++
sort [y | y rest, y >=pivot]
[편집] Prolog
split(H, [A|X], [A|Y], Z) :-
order(A, H), split(H, X, Y, Z).
split(H, [A|X], Y, [A|Z]) :-
not(order(A, H)), split(H, X, Y, Z).
split(_, [], [], []).
quicksort([], X, X).
quicksort([H|T], S, X) :-
split(H, T, A, B),
quicksort(A, S, [H|Y]),
quicksort(B, Y, X).
[편집] 루비
def sort(array)
# return [] if array.empty?
return array if array.size < 2
left, right = array[1..-1].partition { |y| y <= array.first }
sort(left) + [ array.first ] + sort(right)
end
[편집] SML
This example demonstrates the use of an arbitrary predicate in a functional language.
fun quicksort lt lst =
let val rec sort =
fn [] => []
| (x::xs) =>
let
val (left,right) = List.partition (fn y => lt (y, x)) xs
in sort left @ x :: sort right
end
in sort lst
end
[편집] Pascal
program QSort;
const Max = 1000;
var Data: array[1..Max] of integer;
I: Integer;
procedure Sort(l, r: Integer);
var i, j, x, y: integer;
begin
i := l;
j := r;
x := Data[(l+r) DIV 2];
while i<=j do
begin
while Data[i] < x do inc(i);
while x < Data[j] do dec(j);
if i <= j then
begin
y := Data[i];
Data[i] := Data[j];
Data[j] := y;
inc(i);
dec(j);
end;
end;
if l < j then Sort(l, j);
if i < r then Sort(i, r);
end;
begin {QSort}
Randomize;
for i := 1 to Max do Data[i] := Random(30000);
Sort(1, Max);
Writeln;
for i := 1 to Max do Write(Data[i]:8);
end.
[편집] C \ #
public static void Sort(int[] numbers)
{
Sort(numbers, 0, numbers.Length - 1);
}
private static void Sort(int[] numbers, int left, int right)
{
if (left < right)
{
int middle = numbers[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
while (numbers[++i] < middle) ;
while (numbers[--j] > middle) ;
if (i >= j)
break;
Swap(numbers, i, j);
}
Sort(numbers, left, i - 1);
Sort(numbers, j + 1, right);
}
}
private static void Swap(int[] numbers, int i, int j)
{
int number = numbers[i];
numbers[i] = numbers[j];
numbers[j] = number;
}
[편집] VB. Net
Private m_i32ArrSort(10000) As Integer
Private Sub main()
m_vSorting(1, 10000)
End Sub
' Sort
Private Sub m_vSorting(ByVal i32Left As Integer, ByVal i32Right As Integer)
If (i32Left >= i32Right) Then Return
Dim i32I, i32J As Integer
Dim i32Middle = m_i32ArrSort(i32Left)
i32I = i32Left + 1
i32J = i32Right
Do
While (i32I <= i32Right)
If (m_i32ArrSort(i32I) > i32Middle) Then Exit While
i32I += 1
End While
While (i32J > i32Left)
If (m_i32ArrSort(i32J) < i32Middle) Then Exit While
i32J -= 1
End While
If (i32I > i32J) Then Exit Do
m_vSwap(i32I, i32J)
Loop
m_vSwap(i32Left, i32J)
m_vSorting(i32Left, i32J)
m_vSorting(i32J + 1, i32Right)
End Sub
' Swap
Private Sub m_vSwap(ByVal i32I As Integer, ByVal i32J As Integer)
Dim i32Tmp As Integer = m_i32ArrSort(i32I)
m_i32ArrSort(i32I) = m_i32ArrSort(i32J)
m_i32ArrSort(i32J) = i32Tmp
End Sub다음으로 전송:https://www.cnblogs.com/seastarcn/archive/2011/11/29/2267453.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
