快速排序算法实现快速排序|数据结构

本文概述

复杂
算法
C程序
Java程序
C＃程序

快速排序是广泛使用的排序算法, 该算法在平均情况下对n个元素的数组进行n log n个比较。该算法遵循分而治之的方法。该算法以以下方式处理数组。

将数组的第一个索引设置为left和loc变量。将数组的最后一个索引设置为right变量。即left = 0, loc = 0, en d = n-1, 其中n是数组的长度。
从数组的右边开始, 从右到右扫描整个数组, 将数组的每个元素与loc指向的元素进行比较。

如果是这种情况, 则继续进行比较, 直到right等于loc。
如果a [loc]> a [right], 则交换两个值。并转到步骤3。
设置, 位置=右

从左侧指向的元素开始, 并将每个元素的方式与变量loc指向的元素进行比较。确保a [loc]> a [left]

如果是这种情况, 则继续进行比较, 直到loc等于left为止。
[loc] < a [right], 然后交换两个值并转到步骤2。
设置, 位置=左。

复杂

复杂	最好的情况	平均情况	最差的情况
时间复杂度	O（n）用于三向分区或O（n log n）简单分区	O（n log n）	O(n2)
Space Complexity			O(log n)

算法分区（ARR, BEG, END, LOC）

步骤1：[INITIALIZE] SET LEFT = BEG, RIGHT = END, LOC = BEG, FLAG =
步骤2：当FLAG =时, 重复步骤3至6
步骤3：在ARR [LOC] < = ARR [RIGHT]和LOC！= RIGHT的情况下重复设置RIGHT = RIGHT-1 [LOOP结束]
第4步：如果LOC =正确, 则设置标志= 1, 否则, 如果ARR [LOC]> ARR [RIGHT]交换ARR [LOC], 且带有ARR [RIGHT], 则SET LOC = RIGHT [IF结束]
步骤5：如果FLAG = 0, 则当ARR [LOC]> = ARR [LEFT] AND LOC！= LEFT SET LEFT = LEFT + 1 [LOOP LOOP]时重复
步骤6：如果LOC =左置标志= 1其他IF ARR [LOC] < ARR [LEFT]交换ARR [LOC] with ARR [LEFT] SET LOC =左[IF结束] [IF结束]
第7步：[结束循环]
步骤8：结束

QUICK_SORT（ARR, BEG, END）

步骤1：IF（BEG < END）呼叫分区（ARR, BEG, END, LOC）CALL QUICKSORT（ARR, BEG, LOC-1）CALL QUICKSORT（ARR, LOC + 1, END）[IF结束]
步骤2：结束

C程序

#include < stdio.h> int partition(int a[], int beg, int end); void quickSort(int a[], int beg, int end); void main(){ int i; int arr[10]={90, 23, 101, 45, 65, 23, 67, 89, 34, 23}; quickSort(arr, 0, 9); printf("\n The sorted array is: \n"); for(i=0; i< 10; i++) printf(" %d\t", arr[i]); }int partition(int a[], int beg, int end){ int left, right, temp, loc, flag; loc = left = beg; right = end; flag = 0; while(flag != 1) {while((a[loc] < = a[right]) & & (loc!=right))right--; if(loc==right)flag =1; else if(a[loc]> a[right]){temp = a[loc]; a[loc] = a[right]; a[right] = temp; loc = right; }if(flag!=1){while((a[loc] > = a[left]) & & (loc!=left))left++; if(loc==left)flag =1; else if(a[loc] < a[left]){temp = a[loc]; a[loc] = a[left]; a[left] = temp; loc = left; }} } return loc; }void quickSort(int a[], int beg, int end){ int loc; if(beg< end) {loc = partition(a, beg, end); quickSort(a, beg, loc-1); quickSort(a, loc+1, end); }}

【快速排序算法实现】输出：

The sorted array is: 232323344565678990101

Java程序

public class QuickSort {public static void main(String[] args) {int i; int[] arr={90, 23, 101, 45, 65, 23, 67, 89, 34, 23}; quickSort(arr, 0, 9); System.out.println("\n The sorted array is: \n"); for(i=0; i< 10; i++)System.out.println(arr[i]); } public static int partition(int a[], int beg, int end) {int left, right, temp, loc, flag; loc = left = beg; right = end; flag = 0; while(flag != 1){while((a[loc] < = a[right]) & & (loc!=right))right--; if(loc==right)flag =1; elseif(a[loc]> a[right]){temp = a[loc]; a[loc] = a[right]; a[right] = temp; loc = right; }if(flag!=1){while((a[loc] > = a[left]) & & (loc!=left))left++; if(loc==left)flag =1; elseif(a[loc] < a[left]){temp = a[loc]; a[loc] = a[left]; a[left] = temp; loc = left; }}}returnloc; } static void quickSort(int a[], int beg, int end) {int loc; if(beg< end){loc = partition(a, beg, end); quickSort(a, beg, loc-1); quickSort(a, loc+1, end); } }}

输出：

The sorted array is: 232323344565678990101

C＃程序

using System; public class QueueSort{public static void Main() {int i; int[] arr={90, 23, 101, 45, 65, 23, 67, 89, 34, 23}; quickSort(arr, 0, 9); Console.WriteLine("\n The sorted array is: \n"); for(i=0; i< 10; i++)Console.WriteLine(arr[i]); } public static int partition(int[] a, int beg, int end) {int left, right, temp, loc, flag; loc = left = beg; right = end; flag = 0; while(flag != 1){while((a[loc] < = a[right]) & & (loc!=right))right--; if(loc==right)flag =1; else if(a[loc]> a[right]){temp = a[loc]; a[loc] = a[right]; a[right] = temp; loc = right; }if(flag!=1){while((a[loc] > = a[left]) & & (loc!=left))left++; if(loc==left)flag =1; else if(a[loc] < a[left]){temp = a[loc]; a[loc] = a[left]; a[left] = temp; loc = left; }}}return loc; } static void quickSort(int[] a, int beg, int end) {int loc; if(beg< end){loc = partition(a, beg, end); quickSort(a, beg, loc-1); quickSort(a, loc+1, end); } }}

输出：