数据结构与算法之排序(归纳总结二)

浏览数：17 / 时间：2015年06月08日

　　交换类排序主要是通过两两比较待排元素的关键字，若发现与排序要求相逆，则“交换”之。在这类排序方法中最常见的是起泡排序和快速排序，其中快速排序是一种在实际应用中具有很好表现的算法。

1.冒泡排序

a.算法描述

　　起泡排序的思想非常简单。首先，将n个元素中的第一个和第二个进行比较，如果两个元素的位置为逆序，则交换两个元素的位置；进而比较第二个和第三个元素关键字，如此类推，直到比较第n-1个元素和第n个元素为止；上述过程描述了起泡排序的第一趟排序过程，在第一趟排序过程中，我们将关键字最大的元素通过交换操作放到了具有n个元素的序列的最一个位置上。然后进行第二趟排序，在第二趟排序过程中对元素序列的前n-1个元素进行相同操作，其结果是将关键字次大的元素通过交换放到第n-1个位置上。一般来说，第i趟排序是对元素序列的前n-i+1个元素进行排序，使得前n-i+1个元素中关键字最大的元素被放置到第n-i+1个位置上。排序共进行n-1趟，即可使得元素序列按关键字有序。

技术分享

b.算法实现

	public void bubbleSort(int[] r, int low, int high) {
		int n = high - low + 1;
		for (int i = 1; i < n; i++)
			for (int j = low; j <= high - i; j++)
				if (!compare(r[j], r[j + 1])) {
					int temp = r[j];
					r[j] = r[j + 1];
					r[j + 1] = temp;
				}

	}

【效率分析】
空间效率：仅使用一个辅存单元。
时间效率：假设待排序的元素个数为n，则总共要进行n-1趟排序，对j 个元素的子序列进行一趟起泡排序需要进行j-1 次关键字比较，起泡排序的时间复杂度为Ο(n²)。

c.算法示例

BubbleSort.java

package com.test.sort.exchange;


public class BubbleSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		System.out.println("冒泡排序排序功能实现》》》》");
		int[] arr = { 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 };

		BubbleSort sort = new BubbleSort();
		System.out.println("排序之前序列：");
		sort.printArr(arr);
		sort.bubbleSort(arr, 0, arr.length - 1);
		System.out.println("排序之后序列：");;
		sort.printArr(arr);
	}

	public void bubbleSort(int[] r, int low, int high) {
		int n = high - low + 1;
		for (int i = 1; i < n; i++)
			for (int j = low; j <= high - i; j++)
				if (!compare(r[j], r[j + 1])) {
					int temp = r[j];
					r[j] = r[j + 1];
					r[j + 1] = temp;
				}

	}// end of bubbleSort

	public boolean compare(int paramA, int paramB) {
		if (paramA < paramB) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * 依次打印出数组元素
	 */
	public void printArr(int[] arr) {
		if (arr != null) {
			for (int temp : arr) {
				System.out.print(temp + "   ");
			}
			System.out.println();
		}
	}

}

d.结果输出

技术分享

2.快速排序

a.算法描述

　　快速排序是将分治法运用到排序问题中的一个典型例子，快速排序的基本思想是：通过一个枢轴（pivot）元素将n个元素的序列分为左、右两个子序列Ll和Lr，其中子序列Ll中的元素均比枢轴元素小，而子序列Lr中的元素均比枢轴元素大，然后对左、右子序列分别进行快速排序，在将左、右子序列排好序后，则整个序列有序，而对左右子序列的排序过程直到子序列中只包含一个元素时结束，此时左、右子序列由于只包含一个元素则自然有序。用分治法的三个步骤来描述快速排序的过程如下：

　　1. 划分步骤：通过枢轴元素x将序列一分为二，且左子序列的元素均小于x，右子序列的元素均大于x；
　　2. 治理步骤：递归的对左、右子序列排序；
　　3. 组合步骤：无
　　从上面快速排序算法的描述中我们看到，快速排序算法的实现依赖于按照枢轴元素x对待排序序列进行划分的过程。对待排序序列进行划分的做法是：使用两个指针low 和high分别指向待划分序列r的范围，取low所指元素为枢轴，即pivot = r[low]。划分首先从high所指位置的元素起向前逐一搜索到第一个比pivot小的元素，并将其设置到low所指的位置；然后从low所指位置的元素起向后逐一搜索到第一个比pivot大的元素，并将其设置到high所指的位置；不断重复上述两步直到low = high为止，最后将pivot设置到low与high共同指向的位置。使用上述划分方法即可将待排序序列按枢轴元素pivot分成两个子序列，当然pivot的选择不一定必须是r[low]，而可以是r[low..high]之间的任何数据元素。

b.算法实现

//在划分算法的基础上，快速排序算法的递归实现   
 public void quickSort(int[] r, int low, int high) {
        if (low < high) {
            int pa = partition(r, low, high);
            quickSort(r, low, pa - 1);
            quickSort(r, pa + 1, high);
        }
    }
　　//将序列划分为两个子序列并返回枢轴元素的位置
    private int partition(int[] r, int low, int high) {
        int pivot = r[low]; // 使用r[low]作为枢轴元素
        while (low < high) { // 从两端交替向内扫描
            while (low < high && !compare(r[high], pivot))
                high--;
            r[low] = r[high]; // 将比pivot小的元素移向低端
            while (low < high && compare(r[low], pivot))
                low++;
            r[high] = r[low]; // 将比pivot大的元素移向高端

        }
        r[low] = pivot; // 设置枢轴
        return low; // 返回枢轴元素位置
    }

【效率分析】
空间效率：不确定，最坏情况下是n。
时间效率：假设待排序的元素个数为n，则总共要进行n-1趟排序，对j 个元素的子序列进行一趟起泡排序需要进行j-1 次关键字比较，起泡排序的时间复杂度为Ο(n log n)。

c.算法示例

QuickSort.java

package com.test.sort.exchange;

public class QuickSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		System.out.println("快速排序排序功能实现》》》》");
		int[] arr = { 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 };

		QuickSort sort = new QuickSort();
		System.out.println("排序之前序列：");
		sort.printArr(arr);
		sort.quickSort(arr, 0, arr.length - 1);
		System.out.println("排序之后序列：");;
		sort.printArr(arr);
	}

	public void quickSort(int[] r, int low, int high) {
		if (low < high) {
			int pa = partition(r, low, high);
			quickSort(r, low, pa - 1);
			quickSort(r, pa + 1, high);
		}
	}

	private int partition(int[] r, int low, int high) {
		int pivot = r[low]; // 使用r[low]作为枢轴元素
		while (low < high) { // 从两端交替向内扫描
			while (low < high && !compare(r[high], pivot))
				high--;
			r[low] = r[high]; // 将比pivot小的元素移向低端
			while (low < high && compare(r[low], pivot))
				low++;
			r[high] = r[low]; // 将比pivot大的元素移向高端

		}
		r[low] = pivot; // 设置枢轴
		return low; // 返回枢轴元素位置
	}

	public boolean compare(int paramA, int paramB) {
		if (paramA < paramB) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * 依次打印出数组元素
	 */
	public void printArr(int[] arr) {
		if (arr != null) {
			for (int temp : arr) {
				System.out.print(temp + "   ");
			}
			System.out.println();
		}
	}
}