口试之-常用排序算法（冒泡，快排，插入等）

面试之------常用排序算法（冒泡，快排，插入等）

来源：http://blog.****.net/agwujiang/article/details/5829443

（一）冒泡排序（Bubble Sort）

算法描述：每次都将最大的变量交换到最靠右的位置，第N次遍历肯定会将第n大的数字放到合适的位置，总共进行length-1次。

算法实现：

	void bubbleSort(int array[])
	{
		boolean exchange;
		for(int j = 1; j < array.length; ++j)
		{
			exchange = false;
			for(int i = 0; i < array.length -j; ++i)
			{
				if(array[i] > array[i + 1])
				{
					int tmp = array[i];
					array[i] = array[i + 1];
					array[i + 1] = tmp;
					exchange = true;
				}
			}
			if(!exchange) break;
		}
	}

ps:1--在第一层循环中使用了exchange作为排序标志，如果一次遍历无交换，则说明排序完成，可以节省继续无谓的循环遍历。

2--第一层循环的次数为N-1次。

3--第二层循环的次数为array.length-j，以为第j次循环时后j个数字都是排序好的。

（二）快速排序（Quick Sort）

算法描述：每次以给定的起止位置之间的一个变量为基准，排序使基准左边均小于基准，基准右边均大于基准；递归排序基准两侧序列，直至起止位置相同。

算法实现：

	int partition(int array[], int low, int high)
	{
		int pivot = array[low];
		while(low < high)
		{
			while(low < high && array[high] >= pivot)
			{
				--high;
			}
			int tmp = array[low];
			array[low] = array[high];
			array[high] = tmp;
			while(low < high && array[low] <= pivot)
			{
				++low;
			}
			tmp = array[low];
			array[low] = array[high];
			array[high] = tmp;
		}
		return low;
	}
	
	void quickSort(int array[], int low, int high)
	{
		if(low >= 0 && high < array.length && low < high)
		{
			int n = partition(array, low, high);
			quickSort(array, low, n - 1);
			quickSort(array, n + 1, high);
		}
	}

（三）插入排序（Insert Sort）

算法描述：当排序第N个数字的时候假定前N-1个数字是排好序的，只需要依次比较N与之前的数字，将N移动到合适的位置。

算法复杂度： 1 + 2 + 3 …… + n = O(N^2)

算法实现：

	void insertSort(int array[])
	{
		//依次将1-array.length位置的元素放到合适位置
		for(int j = 1; j < array.length; ++j)
		{
			for(int i = j; i > 0 ; --i)
			{
				if(array[i] < array[i - 1])
				{
					int tmp = array[i];
					array[i] = array[i - 1];
					array[i - 1] = tmp;
				}
				else{
					break;
				}
			}
		}
	}

pps(你仔细数标题中横线的数量了吗？)

口试之-常用排序算法（冒泡，快排，插入 等）

相关推荐

口试之-常用排序算法（冒泡，快排，插入等）