【数据结构】快速排序(QuickSortNonR)的非递归实现

叁歲伎倆 2022-06-16 12:56 89阅读 0赞

快速排序的定义：

快速排序(Quick Sort)是一种有效的排序[算法][Link 1]。虽然[算法][Link 1]在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对[快速排序算法][Link 2]进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。

快速排序被认为是当前最优秀的内部排序方法。

实现快速排序的方法有1，左右指针法；2挖坑法；3，前后指针法。

但是那三种方法都需要使用递归的方法，那使用非递归的方法也可以进行快速的排序，不过都要进行其他方法的复用：

首先是插入排序：

void InsertSort(int *a, size_t n)//插入排序
    {
    	for (size_t i = 1; i < n; i++)
    	{
    		size_t j = 0;
    		while (j < i&&a[j] <= a[i])
    		{
    			j++;
    		}
    		if (j < i)
    		{
    			size_t k = i;
    			int tmp = a[i];
    			while (k>j)
    			{
    				a[k] = a[k - 1];
    				k--;
    			}
    			a[k] = tmp;
    		}
    	}
    }

接下来是快速排序中前后指针法：

int GetMidIndex(int *a, int left, int right)//三树取中法
    {
    	int mid = left + (right - left) / 2;
    	if (a[left] < a[mid])
    	{
    		if (a[left]>a[right])
    		{
    			return left;
    		}
    		else if (a[mid] > a[right])
    		{
    			return right;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    	else
    	{
    		if (a[mid] > a[right])
    		{
    			return mid;
    		}
    		else if (a[left] > a[right])
    		{
    			return right;
    		}
    		else
    		{
    			return left;
    		}
    	}
    }
    
    int PartSort3(int *a, int left, int right)
    {
    	assert(a);
    	int mid = GetMidIndex(a, left, right);
    	swap(a[mid], a[right]);
    
    	int prev = left - 1;
    	int cur = left;
    	int key = a[right];
    	while (cur < right)
    	{
    		if (a[cur] < key && ++prev != cur)
    		{
    			swap(a[cur], a[prev]);
    		}
    		++cur;
    	}
    	swap(a[++prev], a[right]);
    	return prev;
    }

下面是完整的代码：

#include<iostream>
    using namespace std;
    #include<assert.h>
    #include<stack>
    
    
    void InsertSort(int *a, size_t n)//插入排序
    {
    	for (size_t i = 1; i < n; i++)
    	{
    		size_t j = 0;
    		while (j < i&&a[j] <= a[i])
    		{
    			j++;
    		}
    		if (j < i)
    		{
    			size_t k = i;
    			int tmp = a[i];
    			while (k>j)
    			{
    				a[k] = a[k - 1];
    				k--;
    			}
    			a[k] = tmp;
    		}
    	}
    }
    
    int GetMidIndex(int *a, int left, int right)//三数取中法
    {
    	int mid = left + (right - left) / 2;
    	if (a[left] < a[mid])
    	{
    		if (a[left]>a[right])
    		{
    			return left;
    		}
    		else if (a[mid] > a[right])
    		{
    			return right;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    	else
    	{
    		if (a[mid] > a[right])
    		{
    			return mid;
    		}
    		else if (a[left] > a[right])
    		{
    			return right;
    		}
    		else
    		{
    			return left;
    		}
    	}
    }
    
    int PartSort3(int *a, int left, int right)
    {
    	assert(a);
    	int mid = GetMidIndex(a, left, right);
    	swap(a[mid], a[right]);
    
    	int prev = left - 1;
    	int cur = left;
    	int key = a[right];
    	while (cur < right)
    	{
    		if (a[cur] < key && ++prev != cur)
    		{
    			swap(a[cur], a[prev]);
    		}
    		++cur;
    	}
    	swap(a[++prev], a[right]);
    	return prev;
    }
    void QuickSort(int *a, size_t left, size_t right)
    {
    	stack<int> s;
    	s.push(right);
    	s.push(left);
    	while (!s.empty())
    	{
    		int begin = s.top();
    		s.pop();
    		int end = s.top();
    		s.pop();
    		if (end - begin < 30)
    		{
    			InsertSort(a + begin, end + begin + 1);
    		}
    		else
    		{
    			int div = PartSort3(a, begin, end);
    			if ((div - 1)>begin)
    			{
    				s.push(div - 1);
    				s.push(begin);
    			}
    			if ((div + 1) < end)
    			{
    				s.push(end);
    				s.push(div + 1);
    			}
    		}
    	}
    }
    
    void printArray(int *a, size_t n)
    {
    	for (size_t i = 0; i < n; i++)
    	{
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    
    int main()
    {
    	int arr[] = { 1, 3, 6, 0, 8, 2, 9, 4, 7, 5 };
    	/*int arr[] = { 49, 38, 65, 97, 76, 13, 27, 49 };*/
    	int n = sizeof(arr) / sizeof(arr[0]);
    	cout << "进行快速排序前：";
    	printArray(arr, n);
    	cout << "进行快速排序后：";
    	QuickSort(arr, 0, n - 1);
    	printArray(arr, n);
    	system("pause");
    	return 0;
    }

运行的结果：

![Center][]

[Link 1]: http://lib.csdn.net/base/datastructure
[Link 2]: http://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=7638866
[Center]: /images/20220616/1a6f90760a9a4bcb8ab529752fbb8333.png