欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序算法总结 博客分类: java 算法排序Java数据结构快速排序 

程序员文章站 2024-03-06 17:27:14
...

排序算法几种分类方式:

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,实际算法使用时,可以多个算法一起使用,以达到更好的效果。如归并排序中,桶排序中,对子串的处理都可以选择其他效率更好的算法。

 

每个算法代码可见:https://github.com/yangwu/JavaDemo