排序算法总结

排序算法几种分类方式：

1，稳定排序和不稳定排序

      如果a==b， 当排序之前a在b的前面，排序后，a仍然在b的前面，则该排序算法为稳定排序算法。否则为不稳定排序算法。

2，非线性时间比较类排序和线性时间非比较类排序算法

      非线性时间比较类排序：通过比较来决定元素间的相对位置，由于比较次数，使其时间复杂度不能

突破O(nlogn)。

      线性时间非比较类排序：不通过比较来决定元素间的相对位置，它可以突破比较排序的时间下限，以线性时间运行。

      

 

几种常见的排序算法介绍：

 

1，选择排序

算法原理：依次在元素间比较，从集合中找出最小的元素，放到集合最前面，再从剩下的集合中找出次小的元素，再放到当前集合最前面；依次循环，把所有的元素排好序。

平均时间复杂度O(n*n)，空间复杂度O(1)。

选择排序是不稳定排序。

// 选择排序：
	public int[] selectSort(int[] nums) {
		long start = System.currentTimeMillis();
		for (int i = 0; i < nums.length; i++) {
			int minIndex = i;
			for (int j = i + 1; j < nums.length; j++) {
				if (nums[j] < nums[minIndex]) {
					minIndex = j;
				}
			}
			swap(nums, i, minIndex);
		}
		System.out.println("Select Sort, count time = " + (System.currentTimeMillis() - start) + "ms");
		return nums;
	}
        private void swap(int[] nums, int x, int y) {
		if (x == y)
			return;
		int temp = nums[x];
		nums[x] = nums[y];
		nums[y] = temp;
	}

 

 

2，快速排序

算法原理：从元素集合中挑选出一个基准(Pivot)，一次遍历之后，把所有大于基准的元素放在基准值的右边，所有小于基准的元素放在基准值的左边。然后递归分别对左边和右边执行同样的操作。

遍历过程如下：首先选定基准，然后分别从左边和右边开始遍历，直至左右相遇则遍历完成。左边开始往右边遍历时，遇到比基准值大的元素，则停下来，右边开始往左边遍历时，遇到比基准值小的元素，则停下来，然后把左右两个元素交换。然后继续遍历，直至相遇。

注意：如果选定的基准是左边第一个元素，则先从右边开始往左遍历，这样能保证停下来时的元素是不大于基准的元素。反之，则从左边开始遍历。

平均时间复杂度O(nlogn)，空间复杂度O(logn)。

快速排序是不稳定排序

// 快速排序：
	public int[] quickSort(int[] nums) {
		long start = System.currentTimeMillis();
		if (nums == null || nums.length == 0)
			return nums;
		quickSortByPivot(nums, 0, nums.length - 1);
		System.out.println("Quick Sort, count time = " + (System.currentTimeMillis() - start) + "ms");
		return nums;
	}

	private void quickSortByPivot(int[] nums, int left, int right) {
		int l = left, r = right;
		int pivot = nums[left];

		while (l < r) {
			while (r > l && nums[r] >= pivot)
				r--;

			while (r > l && nums[l] <= pivot)
				l++;

			if (l < r)
				swap(nums, l, r);
		}
		swap(nums, left, l);

		if (l - 1 > left)
			quickSortByPivot(nums, left, l - 1);
		if (right > l + 1)
			quickSortByPivot(nums, l + 1, right);
	}

 

 

3，简单插入排序

算法原理：把当前元素插入到已排好序的元素集合的对应位置。把第一个元素当成已经排好序的元素，从第二个元素(新元素)开始，从排好序的元素(待比较元素)中后向前逐一扫描比较，如果待比较的元素比新元素大，则把新元素与待比较元素交换，然后新元素继续往前比较，直至结束。当每个元素都与排好序的元素完成比较，则排序完成。

平均时间复杂度O(n*n)，空间复杂度O(1)。

简单插入排序是稳定排序

// 简单插入排序：
	public int[] simpleInsertSort(int[] nums) {
		long start = System.currentTimeMillis();
		for (int i = 1; i < nums.length; i++) {
			int pre = i - 1, cur = i;
			while (pre >= 0 && nums[pre] > nums[cur]) {
				swap(nums, pre, cur);
				cur = pre;
				pre--;
			}
		}
		System.out.println("Simple Insert Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
		return nums;
	}

 

     

4，希尔(shell)排序(缩小增量排序)

算法原理：是插入排序的改进版，考虑到插入排序时，有可能某个元素需要插入到比较远的位置，导致不断的重复插入。因此希尔排序会优先比较距离较远的元素。希尔排序引入步长概念，先选定一个步长(可根据集合大小确定)，然后使用插入排序思想比较相隔步长距离的各个元素。然后把步长减一，继续比较，直至步长为1，此时相当于插入排序，但是目前的集合已经近似有序了。

平均时间复杂度O(n^1.3)，空间复杂度O(1)。

希尔排序是不稳定排序。

// 希尔排序 ，
	public int[] shellSort(int[] nums) {
		long start = System.currentTimeMillis();
		if (nums == null || nums.length == 0)
			return null;
		int gap = nums.length / 3;// 步长

		while (gap > 0) {
			for (int k = 0; k < gap; k++) {
				int cur = k;
				int pre = k;
				while (cur < nums.length) {
					if (nums[cur] < nums[pre]) {
						swap(nums, cur, pre);
					}
					pre = cur;
					cur += gap;
				}
			}
			gap--;
		}
		System.out.println("Shell Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
		return nums;
	}

 

 

5，冒泡排序

算法原理：每次遍历一次集合，比较相邻元素，把较大的元素移到后面，完成一次遍历时，则最大的元素已经移到最后，然后继续遍历剩下的无序集合，把当前集合最大的移到最后面。经历n次遍历后，完成排序。

冒泡排序还可以稍微改进，当排序过程中，发现待排序集合已经是有序的，则可以不需要进一步遍历了。

平均时间复杂度O(n*n)，空间复杂度O(1)。

冒泡排序是稳定排序。

// 冒泡排序:
	public int[] bubbleSort(int[] nums) {
		long start = System.currentTimeMillis();
		if (nums == null || nums.length == 0)
			return null;
		for (int i = 0; i < nums.length; i++) {
			boolean isSorted = true;// 假设当前已经有序,冒泡排序改进，如果当前循环发现已经有序，则不需要继续遍历。
			for (int j = 1; j < nums.length - i; j++) {
				if (nums[j] < nums[j - 1]) {
					swap(nums, j, j - 1);// 一次遍历后，如果有交换动作，则不是有序的.
					isSorted = false;
				}
			}
			System.out.println("bubble Sort current index:" + i);
			if (isSorted)
				return nums;
		}
		System.out.println("Bubble Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
		return nums;
	}

 

 

6，堆排序

算法原理：堆排序是利用堆这种数据结构来设计的排序算法。堆可以看做一个近似完全二叉树的结构。堆分为大顶堆和小顶堆。大顶堆满足如下性质，父节点的值总是大于(等于)子节点的值，小顶堆满足如下性质，父节点的值总是小于(等于)子节点的值。

从0开始对堆中的节点进行编号，则其节点和其父节点以及子节点的编号关系如下，当前节点编号为i:

父节点编号 parent(i) = i / 2;

左子节点编号 left(i) = 2 * i + 1;

右子节点编号 right(i) = 2 * i + 2;

堆排序过程为首先根据集合元素大小建立一个大顶堆，当前的堆是无序的，然后对每个元素进行调整，使其符合大顶堆的规则，当前节点值大于等于子节点值。完成一次堆的调整后，堆的第一个元素，即堆顶元素，则为集合中的最大元素。此时堆顶元素为有序元素，把它与集合中的最后一个位置的元素互换，然后继续为剩下的其他元素创建大顶堆。直至最后，所有的元素都为有序元素。

平均时间复杂度O(nlogn)，空间复杂度O(1)。

堆排序是不稳定排序。

// 最大堆排序：
	public int[] heapSort(int[] nums) {
		long start = System.currentTimeMillis();
		if (nums == null || nums.length == 0)
			return null;

		buildMaxHeap(nums);

		System.out.println("Heap Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
		return nums;
	}

	private void adjustHeapOfIndex(int[] nums, int index, int heapSize) {
		// System.out.println("index|heapSize:" + index + "|" + heapSize);
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		int largest = index;
		if (left < heapSize && nums[left] > nums[largest])
			largest = left;
		if (right < heapSize && nums[right] > nums[largest])
			largest = right;
		if (index != largest) {
			swap(nums, index, largest);
			adjustHeapOfIndex(nums, largest, heapSize);
		}
		// this.printArrays("adjust heap", nums);
	}

	private int[] buildMaxHeap(int[] nums) {

		int heapSize = nums.length;

		while (heapSize > 0) {// 从nums.length到1，不断构建最大堆；

			// 构建最大堆；
			for (int i = heapSize - 1; i >= 0; i--) { // 针对每个index,不断调整堆;
				adjustHeapOfIndex(nums, i, heapSize);
			}
			// this.printArrays("build max heap:",nums);
			swap(nums, 0, heapSize - 1); // 堆构建完成后 最大的值为nums[0],完后交换放到最后

			heapSize--;
		}

		return nums;
	}

 

 

7，归并排序

 算法原理：归并排序主要是采用分治法，把两个已排好序的子集合合并成一个有序的集合。子集的排序则是采用递归方法，如果子集只包含一个元素，则为一个有序的集合。

平均时间复杂度O(nlogn)，空间复杂度O(n)。

归并排序是稳定排序。

// 归并排序
	public int[] mergeSort(int[] nums) {
		long start = System.currentTimeMillis();
		if (nums == null || nums.length == 0)
			return null;
		// System.out.println("start to merge sort:");
		int[] temp = new int[nums.length];
		mergeSort(nums, 0, nums.length - 1, temp);
		System.out.println("Merge Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
		return nums;
	}

	public void mergeSort(int[] nums, int start, int end, int[] temp) {
		if (end - start > 0) {
			int sublength = (end - start) / 2;
			mergeSort(nums, start, start + sublength, temp);// 分别把两个子串排好序 即一直划分到只剩一个元素，则就是一个排好序的子串。
			mergeSort(nums, start + sublength + 1, end, temp);
			// System.out.println("Merge Sort:" + start + "|" + sublength + "|" + end);
			mergeArrays(nums, start, start + sublength, start + sublength + 1, end, temp);// 把两个排好序的子串合并
		}
	}

	private int[] mergeArrays(int[] nums, int lstart, int lend, int rstart, int rend, int[] temp) {
		if ((lend - lstart) < 0 && (rend - rstart) < 0)
			return nums;

		int tempindex = lstart;
		int leftindex = lstart, rightindex = rstart;
		// System.out.println("tempindex|leftindex " + tempindex + "|" + leftindex);
		while (leftindex <= lend && rightindex <= rend) {
			if (nums[leftindex] <= nums[rightindex]) {
				temp[tempindex++] = nums[leftindex++];
			} else {
				temp[tempindex++] = nums[rightindex++];
			}
		}

		while (leftindex <= lend) {
			temp[tempindex++] = nums[leftindex++];
		}
		while (rightindex <= rend) {
			temp[tempindex++] = nums[rightindex++];
		}
		// System.out.println("fininsh index " + tempindex + "|" + leftindex);
		for (int k = lstart; k <= rend; k++) {// 把经过处理的数组里的值全部更新到原数组中
			nums[k] = temp[k];
		}
		// this.printArrays("Merge Arrays:", nums);
		return nums;
	}

 

 

8，基数排序

算法原理：基数排序是把待排序的数字分为低位和高位，低位先排序，然后收集，再按高位排序，再收集，直至最高位，则排序完成。注意基数排序无法处理负数。

排序过程为，首先得到集合中的最大数，根据最大数，得到需要按位循环排序的次数。

在每次按位排序时，先初始化10个桶，分别存放余数为0-9的元素个数，在一次遍历之后，10个桶中已保存各个余数出现的次数，然后再根据余数个数更新10个桶中的相应元素应该存放的位置，比如余数为1的元素会排在余数为0的元素的后面，因此如果余数为0的元素个数为5，则余数为1的元素至少会在第5个位置之后，由此统计元素应该在集合中出现的位置。

之后再次从大到小遍历整个集合，根据元素的余数，得到对应桶的值，即为该元素在新的集合中的下标值，存放好一个元素，就把对应桶中的值相应减一。遍历结束，则这次按位排序结束，得到一个按低位排序的集合。

再取较高位，进行排序。直至按最高位排序结束，则此时得到的集合就是一个有序的集合。

平均时间复杂度O(2n*k)，k为按位排序的次数；空间复杂度O(n+k)，k为桶的数量；数据量大的话，k会远远小于n。 

基数排序是稳定排序。

// 基数排序 基数排序不能处理负数；
	public int[] radixSort(int[] nums) {
		long start = System.currentTimeMillis();
		if (nums == null || nums.length == 0)
			return null;

		int max = nums[0];
		for (int cur : nums) {// 先得到最大数
			if (cur > max)
				max = cur;
		}

		int[] temp = new int[nums.length];

		int exp = 1;
		do {
			int[] buckets = new int[10];// 针对余数的桶 统计余数个数
			for (int j = 0; j < nums.length; j++) {
				buckets[(nums[j] / exp) % 10]++;// 保存每个余数出现的个数
			}
			// this.printArrays("buckets nums of exp:" + exp, buckets);

			for (int l = 1; l < 10; l++) {
				buckets[l] += buckets[l - 1];// 统计余数对应的数按顺序出现在整个数组中的位置 即余数越小 则其在数组中排在越前面
			}
			// this.printArrays("buckets:", buckets);

			// this.printArrays("before bucket:", nums);
			// 从数组最后往前循环 因为buckets中数据的位置从大到小递减.
			for (int m = nums.length - 1; m >= 0; m--) {
				// System.out.println("m, value:" + m + "|" + nums[m] + "|" +
				// buckets[(nums[m]/exp)%10]);
				// this.printArrays("nums:", nums);
				temp[buckets[(nums[m] / exp) % 10] - 1] = nums[m];// 每存储一个数据后，则把buckets中对应的数据减一；
				buckets[(nums[m] / exp) % 10]--;
				// this.printArrays("buckets:", buckets);
			}

			for (int k = 0; k < nums.length; k++) {// 更新值
				nums[k] = temp[k];
			}

			// this.printArrays("After bucket:" + exp, temp);
			exp *= 10;
		} while (max / exp > 0);

		System.out.println("Radix Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
		return nums;
	}

 

 

9，计数排序

算法原理：计数排序不是基于比较，而是将待排序的数据转换为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求待排序的数据必须是有确定范围的整数。

排序过程为，先得到待排序数据中的最大值和最小值，然后根据最大值和最小值开辟一个新的数组空间，然后遍历整个数据集合，统计各个元素出现的次数，并且存入与元素值对应的数组下标。

然后对数组中的计数进行统计，计算出每个元素应该存放的位置，最后反向遍历数据集合，根据每个元素值，在数组中获取元素应该存放的位置。

平均时间复杂度O(n+k)，空间复杂度(n+k)。k为数据集合中最大值和最小值的范围。如果待排序集合数据比较集中，计算排序是一个很有效的排序算法。

计算排序是稳定排序。

 

// 计数排序
	public int[] countingSort(int[] nums) {
		long start = System.currentTimeMillis();
		if (nums == null || nums.length == 0)
			return null;
		// 先得到待排序数据的范围
		int min = nums[0], max = nums[0];
		for (int curvalue : nums) {
			if (curvalue < min)
				min = curvalue;
			if (curvalue > max)
				max = curvalue;
		}

		// 根据数据范围初始化数组 进行计数
		int[] counts = new int[max - min + 1];

		// 遍历数组 进行计数
		for (int k : nums) {
			counts[k - min]++;
		}

		// 更新数组中各元素的位置
		for (int k = 1; k < counts.length; k++) {
			counts[k] += counts[k - 1];
		}

		this.printArrays("Counting arr:", counts);

		int[] temp = new int[nums.length];
		for (int i = nums.length - 1; i >= 0; i--) {
			// System.out.println("counts index:" + (nums[i]-min) + ",count value:" +
			// counts[nums[i]-min]);
			temp[counts[nums[i] - min] - 1] = nums[i];
			counts[nums[i] - min]--;
		}

		for (int j = 0; j < nums.length; j++) {// 更新值
			nums[j] = temp[j];
		}

		System.out.println("Counting Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
		return nums;
	}

 

 

10，桶排序

算法原理：桶排序是计数排序的升级版，利用函数的映射关系，把数据映射到有限的桶中，然后对每个桶进行单独排序，可使用快速排序等其他算法。最后把几个桶的元素合并，完成排序。

桶排序的时间复杂度取决于各个桶的排序算法，其他部分的时间复杂度为O(n)。显然，桶划分得越多，各个桶中的数据越少，每个桶的排序时间越少，效率越高，但相应的，空间消耗也越大。

平均时间复杂度O(n+k)，空间复杂度O(n+k)。

 

// 桶排序算法
	public int[] bucketSort(int[] nums) {
		long start = System.currentTimeMillis();
		if (nums == null || nums.length == 0)
			return null;
		if (nums.length <= 1)
			return nums;

		//this.printArrays("bucket sort:", nums);
		// 先得到待排序数据的范围
		int min = nums[0], max = nums[0];
		for (int curvalue : nums) {
			if (curvalue < min)
				min = curvalue;
			if (curvalue > max)
				max = curvalue;
		}

		// 根据数的范围 确定桶的个数 以及桶的映射函数
		// 在此假设最多分十个桶 然后把数据分别放入对应桶内
		// 每个桶使用List
		int bucketNum = 10;
		int step = 0;
		if ((max - min) < 10)
			bucketNum = max - min + 1;
		step = (max - min + 1) / bucketNum;// 根据bucketNum和step分出bucketNum个桶，范围 [min,min+step)，最后一个桶还包含剩下的余数;
		// 初始化桶
		List[] buckets = new ArrayList[bucketNum];
		for (int bk = 0; bk < buckets.length; bk++) {
			buckets[bk] = new ArrayList();
		}
		System.out.println("Bucketnum:" + bucketNum);
		// 遍历数组 把元素分别放入桶中
		for (int curnum : nums) {
			int curindex = (curnum - min) / step;
			if (curindex > buckets.length - 1)
				curindex = buckets.length - 1;
			System.out.println("curnum:" + curnum + ",curindex = " + curindex + ",min = " + min + ",step = " + step);
			buckets[curindex].add(curnum);
		}

		// 分别对各个桶进行排序 并且把每个桶中各元素合并
		int index = 0;
		for (List list : buckets) {
			int[] temp = new int[list.size()];
			for (int k = 0; k < list.size(); k++) {
				temp[k] = (Integer) list.get(k);
			}
			int[] tempresult = bucketSort(temp);
			if (tempresult != null)
				for (int value : tempresult)
					nums[index++] = value;
		}

		System.out.println("Bucket Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
		return nums;
	}

 

 

排序算法总结：

1，如果待排序的集合规模较小，如n<50，可用简单插入排序或者选择排序。

2，如果待排序的集合基本有序，可用简单插入排序或者冒泡排序。

3，如果待排序的集合规模较大，则应采用时间复杂度O(nlogn)的排序方法，如快速排序，堆排序或归并排序。

     当待排序的元素是随机分布的，快速排序是平均时间最短的；

     堆排序虽然时间复杂度跟快速排序一样，但是实际上的时间消耗(建堆，调整堆)会比快速排序多，因此一般选择快速排序。

     但是相比快速排序，堆排序的空间的优点是占用更少，也不像快速排序，会出现最坏的情况。

     如果需要稳定的排序算法，则可选归并排序。

4，堆排序适用于在一个集合n中，快速找出前m个元素(m<n)，每次建堆，调整堆，都找出一个元素，执行m次则找出前m个元素。

5，如果待排序的数据比较集中。则可以采用计数排序。

6，实际算法使用时，可以多个算法一起使用，以达到更好的效果。如归并排序中，桶排序中，对子串的处理都可以选择其他效率更好的算法。