快速排序算法实现

本文概述

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

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

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

Ensure that, a[loc] is less than a[right].

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

1. 从左侧指向的元素开始, 并将每个元素的方式与变量loc指向的元素进行比较。确保a [loc]> a [left]
1. 如果是这种情况, 则继续进行比较, 直到loc等于left为止。
2. [loc] <a [right], 然后交换两个值并转到步骤2。
3. 设置, 位置=左。

复杂

算法

分区（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: 
23
23
23
34
45
65
67
89
90
101

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: 
23
23
23
34
45
65
67
89
90
101

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);
		}
	}
}

输出：

The sorted array is: 
23
23
23
34
45
65
67
89
90
101