程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 快速排序-c++(分別用數組和容器實現)

快速排序-c++(分別用數組和容器實現)

編輯:C++入門知識

/**********************************************************************
*版權所有 (C)2014, cheng yang。
*
*文件名稱:快速排序.cpp 數組實現
*內容摘要:無
*其它說明:無
*當前版本: V1.0
*作    者:cheng yang
*完成日期: 20140625
*
*  版本       修改時間     修改人           修改內容
********************************************************************
*   V1.0        20140625    cy			   創建
**********************************************************************/
#include
#include 
using namespace std;
inline void swap(int &a, int &b)//是取地址,是要修改數組的!!!!!
{
	int iTemp = a;
	a = b;
	b = iTemp;
}
/**********************************************************************
*功能描述:數組的劃分
*輸入參數:數組,數組首下標,數組尾下標
*輸出參數:無
*返回值:主元下標
*其它說明:無
*修改日期        版本號            修改人         修改內容
* --------------------------------------------------------------
*
***********************************************************************/

int Partition(int ArrayInput[],int iFirst, int iLast)
{
	int iKey = ArrayInput[iLast];
	int j = iFirst-1 ;
	for (int i = iFirst; i != iLast; i++)
	{
		if (ArrayInput[i] <= iKey)
		{
			j++;
			if (j != i)
			{
				swap(ArrayInput[j], ArrayInput[i]);

			}
		}
	}
	swap(ArrayInput[iLast], ArrayInput[j + 1]);
	return j + 1;
}
/**********************************************************************
*功能描述:quick sort
*輸入參數:數組,數組首下標,數組尾下標
*輸出參數:無
*返回值:無
*其它說明:無
*修改日期        版本號            修改人         修改內容
* --------------------------------------------------------------
*
***********************************************************************/
void QuickSort(int ArrayInput[],int iFirst, int iLast)
{
	
	if (iFirst < iLast)
	{
		int iIndex = Partition(ArrayInput,iFirst, iLast);
		QuickSort(ArrayInput, iFirst, iIndex - 1);
		QuickSort(ArrayInput,iIndex + 1, iLast);
	}
}

/****************************************************************
*功能描述:  主函數                                             *
*輸入參數:  無                                                 *
*輸出參數:  無                                                 *
*返回值  :無                                                 *
*其他說明:  無                                                 *
*修改日期        版本號       修改人        修改內容
* ------------------------------------------------------------------
*
****************************************************************/

int main()
{
	int ArrayInput[10] = { 2, 4, 1, 5, 11, 6, 9, 16, 23, 10 };
	int iFirst = 0;
	int iLast = 9;
	QuickSort(ArrayInput,iFirst, iLast);

	int i = 0;
	while (i < 10)
	{
		cout << ArrayInput[i++] << endl;
	}
	system("pause");
}


容器實現

#include 
#include 
using namespace std;

inline void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}


template
int Partition(vector& a, int istart, int iend)
{
	int ipivot = a[iend];
	int i = istart - 1;
	for (int j = istart; j != iend; j++)
	{
		if (a[j] <= ipivot)
		{
			i++;
			if (i != j)
			{
				swap(a[i], a[j]);
			}
		}
	}
	swap(a[iend], a[i + 1]);
	return i + 1;
}


template
void QuickSort(vector& a, int istart, int iend)
{
	if (istart< iend)
	{
		int ipivot_pos = Partition(a, istart, iend);
		QuickSort(a, istart, ipivot_pos - 1);
		QuickSort(a, ipivot_pos + 1, iend);
	}

}
int main()
{
	vector a;
	int input{ 0 };
	while (cin >> input)
		a.push_back(input);
	int istart = 0;
	int iend = a.size()-1;//輸入6個數,大小是6,數組下標別忘了減1啊
	 
	QuickSort(a, istart, iend);
	for (auto i = a.begin(); i != a.end(); i++)
	{
		cout << *i << endl;
	}
	system("pause");
	return 0;
}




  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved