首页 > 代码库 > 冒泡排序和快速排序

冒泡排序和快速排序

#include <stdio.h>
#include <iostream>
#include <string>
#include <stack>

using std::cout;
using std::endl;
using std::string;
using std::stack;

int arr1[10] = {3,5,2,8,6,1,4,0,9,7};
int arr2[10] = {3,5,2,8,6,1,4,0,9,7};

void print_arr(int arr[], int size)
{
	for(int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");

	return ;
}


void bubble_sort(int arr[], int size)
{
	int i,j,tmp;

	for (i = size; i > 0; i--)
	{
		for (j = 1; j < i; j++)
		{
			if (arr[j] < arr[j-1])
			{
				tmp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = tmp;
			}
		}
	}

	return ;
}

void quick_sort(int arr[], int start, int end)
{
	if (start > end)
		return ;

	int i = start;
	int j = end;
	int pivot = arr[i];

	while (i < j)
	{
		while(i < j && pivot <= arr[j] )
		{
			j--;
		}

		if (i < j)
			arr[i++] = arr[j];

		while(i < j && arr[i] < pivot)
		{
			i++;
		}

		if (i < j)
		{
			arr[j--] = arr[i];
		}
	}

	arr[j] = pivot;

	
	quick_sort(arr, start, i-1);
	quick_sort(arr, i+1, end);

	return ;
}




void main()
{
	bubble_sort(arr1, 10);
	quick_sort(arr2, 0, 9);

	print_arr(arr1, 10);
	print_arr(arr2, 10);
	
	string str("Hi Welcome to cricode");
	stack<char> cstack;
	stack<char> tmp;
	int index = 0;

	for (index = 0; index < str.size(); index++)
	{
		cstack.push(str[index]);
	}

	index = 0;
	while(!cstack.empty())
	{
		if (' ' == cstack.top())
		{
			while(!tmp.empty())
			{
				str[index++] = tmp.top();
				tmp.pop();
			}
			str[index++] = ' ';
			cstack.pop();
		}
		else
		{
			tmp.push(cstack.top());
			cstack.pop();
		}
	}

	while(!tmp.empty())
	{
		str[index++] = tmp.top();
		tmp.pop();
	}

	cout<<str<<endl;
	getchar();
}



冒泡排序和快速排序