个性化阅读
专注于IT技术分析

快速排序算法实现

点击下载

本文概述

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

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

复杂

复杂 最好的情况 平均情况 最差的情况
时间复杂度 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: 
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
赞(0)
未经允许不得转载:srcmini » 快速排序算法实现

评论 抢沙发

评论前必须登录!