排序算法

| 分类 PIECE  | 标签 排序算法 

[TOC]

1. 交换排序法

## 1.1 冒泡排序

原理：冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟遍历后，最大的数放在最后，第二趟遍历后，倒数第二大数放在倒数第二的位置，……重复以上过程，直至最终完成排序。尽管这个算法是最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。

性能分析：稳定排序。改进算法：添加一个标志——是否需要继续比较，如果在该趟比较中未发生一次数据交换则结束排序，否则进行下一趟比较。最坏情况下需要n(n-1)/2次比较和记录移动。时间复杂度为O(img)。

public static <T extends Comparable<? super T>> void sort2(T[] data) {
	int len = data.length; 	// 数组长度
	for (int i = len - 1; i > 0; --i) {
		T temp = null; 	// 临时变量
		boolean isExchanged = false; 	// 交换标志,false表示未交换
		for (int j = 0; j < i; ++j) {
			// 如果data[j]大于data[j + 1],交换
			if (data[j].compareTo((T) data[j + 1]) > 0) {
				temp = data[j];
				data[j] = data[j + 1];
				data[j + 1] = temp;
				isExchanged = true;	// 发生了交换,故将交换标志置为真
			}// end if
		}// end for
		// 本趟排序未发生交换,提前终止算法,提高效率
		if (!isExchanged) {
			return;
		}// end if
	}// end for
}

1.2 快速排序

原理：是对冒泡排序的一种改进。任取待排序元素序列中某个元素作为基准码，按照该基准码将整个序列划分为左右两个子序列：左侧子序列所有数据都小于基准码，右侧子序列所有数据都大于或等于基准码，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

性能分析：不稳定排序。时间复杂度为O(img)。存储开销O(img)。总的排序码比较次数为img。

private static <T> void swap(T[] array, int i, int j) {
  T tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
}

private static <T extends Comparable<? super T>> int partition(T[] array, int begin, int end) {
  int i = begin - 1;
  T pivot = array[end];
  for (int j = begin; j < end; ++j) {
    if (array[j].compareTo(pivot) <= 0) {
      swap(array, ++i, j);
    }
  }
  swap(array, ++i, end);   
  return (i);
}

public static <T extends Comparable<? super T>> void qsort(T[] array, int begin, int end) {
  if (end > begin) {
    int index = partition(array, begin, end);
    qsort(array, begin, index - 1);
    qsort(array, index + 1, end);
  }
}

1.3 鸡尾酒排序

原理：鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目。以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。

性能分析：鸡尾酒排序最糟或是平均所花费的次数都是O(img)，但如果序列在一开始已经大部分排序过的话，会接近O(n)。

public static <T extends Comparable<? super T>> void cocktailSort(T[] data) {
  int begin = 0;
  int end = data.length - 1;
  boolean isSwap = true;
  T temp;
  // if no elements have been swapped, then the list is sorted
  while (isSwap == true){
    isSwap = false;
    for(int i = begin; i < end; ++i){
      // test whether the two elements are in the correct order
      if(data[i].compareTo(data[i + 1]) > 0){
        // let the two elements change places
        temp = data[i];
        data[i] = data[i + 1];
        data[i + 1] = temp;
        isSwap = true;
      }
    }
    // decreases end the because the element with the largest value in the unsorted
    // part of the list is now on the position top
    end = end - 1;
    for(int i = end; i > begin; --i){
      if(data[i].compareTo(data[i - 1]) < 0){
        temp = data[i];
        data[i] = data[i - 1];
        data[i - 1] = temp;
        isSwap = true;
      }
    }
    // increases begin because the element with the smallest value in the unsorted
    // part of the list is now on the position bottom
    begin = begin + 1; 
  }
}

2. 插入排序法

2.1 直接插入排序

原理：把数列中待排序的n个元素看成一个有序表和一个无序表，开始时有序表中只包含第一个元素，无序表包含n-1个。第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

性能分析：稳定排序。最坏情况元素比较和移动分别为img，时间复杂度为O(img)。

public static <T extends Comparable<? super T>> void sort(T[] data){
    T temp = null;  // 临时变量
    int j;
    for (int i = 1; i < data.length; ++i){
        //逆序查找插入位置，否则留置原位
        if (data[i].compareTo((T) data[i - 1]) < 0){
            temp = data[i];
            j = i - 1;
            do {
                data[j + 1] = data[j];
                --j;
            } while (j >= 0 && temp.compareTo(data[j]) < 0);
            data[j + 1] = temp;
        }//end if
    }//end for
}//end sort

2.2 希尔排序

原理：希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了。

性能分析：不稳定排序。大量实验证明，对于规模较大的序列（n <= 1000）有很高的效率。排序码平均比较次数和元素平均移动次数大约在img到1.6img范围内。

public static <T extends Comparable<? super T>> void sort(T[] data){
    int len = data.length;  //数组长度
    int gap = len;  //间隔宽度
    int i, j;
    T temp = null;  //临时变量

    do {  
        gap = gap / 3 + 1;
        for (i = gap; i < data.length; ++i){
            if(data[i].compareTo(data[i - gap]) < 0){
                temp = data[i];
                j = i - gap;
                do {
                    data[j + gap] = data[j];
                    j = j - gap;
                }while (j > 0 && temp.compareTo(data[j]) < 0);
            data[j + gap] = temp;
            }
        }
    }while (gap > 1);
}

3. 选择排序

3.1 简单选择排序

原理：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

性能分析：不稳定排序。最坏情况元素比较和移动分别为n(n-1)/2，3(n-1)，时间复杂度为O(img)。

public static <T extends Comparable<? super T>> void sort(T[] data){
    int len = data.length;
    int k, j;
    T temp;  //临时变量
    for (int i = 0; i < len - 1; ++i){ //遍历从第一个到倒数第二个
        k = i;
        for (j = i + 1; j < len; ++j){ //遍历从第i+1到最后一个
            if (data[j].compareTo(data[k]) < 0){
                k = j;
            }
        }//end for
        if (k != i){ //如果k不变，说明data[k]是最小，不需要交换
            temp = data[i];
            data[i] = data[k];
            data[k] = temp;
        }//end if
    }//end for
}

上一篇     下一篇