赞
踩
快速排序
最简单的快排。
以头元素作为标记元素,将大于标记元素的数字放在其的右边,小于的放在其左边。之后对于左边和右边的分别排序。
parttitioned (input list[], input left, input right)
pivot <- list[left]
i <- left
j <- right
while (i < j) do
whlie (i < j and list[j] >= pivot) do
j <- j - 1
end
if (i < j)
list[i] <- list [j]
whlie (i < j and list[i] < pivot) do
i <- i + 1
end
if (i < j)
list[j] <- list [i]
end
list[i] <- pivot
return i
quicksort (input list[], input left, input right)
if (left < right)
mid = parttitioned(list, left, left)
quicksort (list, left, mid-1)
quicksort (list, mid+1, right)
end if
c/c++
- int partitionsed (int a[], int left, int right)
- {
- int pivot = a[left];
- int i = left,j = right;
- int k;
- while (i < j)
- {
- while (i < j && a[j] >= pivot)
- j--;
- if (i < j)
- a[i] = a[j];
- while (i < j && a[i] < pivot)
- i++;
- if (i < j)
- a[j] = a[i];
- }
- a[i] = pivot;
- return i;
- }
- void quicksort(int a[],int left,int right)
- {
- if (left < right)
- {
- int insert = partitionsed(a,left,right);
- quicksort (a,left,insert-1);
- quicksort (a,insert+1, right);
- }
- }
python
- def partitioned(list, left, right):
- pivot = list[left]
- i = left
- j = right
- while i < j:
- while i < j and list[j] >= pivot:
- j = j - 1
- if i < j:
- list[i] = list[j]
- while i < j and list[i] < pivot:
- i = i + 1
- if i < j:
- list[j] = list[i]
- list[i] = pivot
- return i
- def QuickSort(list, left, right):
- if (left < right ):
- mid = partitioned(list, left, right)
- QuickSort(list, left, mid-1)
- QuickSort(list, mid+1,right)
-
- list = [5, 1, 7, 3, 7, 0, 4, 8, 6, 9]
- QuickSort(list, 0, 9)
- print list
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。