排序算法几种分类方式：
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，实际算法使用时，可以多个算法一起使用，以达到更好的效果。如归并排序中，桶排序中，对子串的处理都可以选择其他效率更好的算法。
相关推荐
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
《十大经典排序算法总结》 排序算法是计算机科学的基础，其设计思想和效率对软件的性能有着直接影响。本文主要探讨了十种经典的排序算法，包括它们的设计思路、优缺点以及适用场景，帮助我们理解排序算法的核心。 ...
C#排序算法总结涵盖了交换排序和插入排序两大类排序算法，其中交换排序包括了冒泡排序、选择排序和快速排序，而插入排序则涉及直接插入排序和折半插入排序。下面将详细介绍每种排序算法的实现原理、特点以及在C#中的...
在这个名为“各种排序算法总结（ppt）”的资料中，我们将会深入探讨多种常见的排序算法，包括它们的基本原理、优缺点以及实际应用。** 首先，我们要了解排序的目的是为了使数据有序，这在数据处理和分析中具有广泛...
【排序算法总结】 排序是计算机科学中的一项基本操作，它涉及到如何有效地重新排列一组数据，使其按照特定的顺序排列。本文将重点介绍八大排序算法，包括插入排序、希尔排序、交换排序、快速排序、选择排序、堆排序...
排序算法总结——最全、最新的排序算法 本文对各种排序算法进行了总结，包括插入排序、选择排序、冒泡排序、快速排序和堆排序等。下面是对每种排序算法的详细介绍： 一、插入排序（Insertion Sort） 插入排序是一...
【排序算法总结】 排序算法是计算机科学中处理数据排列的重要工具，主要分为稳定排序和非稳定排序、内排序和外排序两大类。稳定排序保证了相同元素在排序后的相对位置不变，而非稳定排序则不作此保证。内排序是指...
排序算法是计算机科学中的基础概念，用于组织和整理数据，使其按照特定顺序排列。以下是对几种常见排序算法的详细说明： 1. 插入排序： 插入排序是一种简单的排序算法，其时间复杂度为O(n^2)。它通过将每个元素...
### 常用排序算法总结 #### 一、冒泡排序 冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，依次比较相邻的两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行的，直到没有再需要...
八大经典排序算法总结和源代码 在计算机科学中，排序算法是最基本也是最重要的算法之一。排序算法的性能直接影响到整个系统的性能。今天，我们将总结八大经典排序算法，并提供C++实现的源代码。 一、稳定排序和...
"八种常见排序算法总结" 直接插入排序是一种简单的排序算法，它的思想是每次选择一个元素 K 插入到之前已排好序的部分 A[1…i]中，插入过程中 K 依次由后向前与 A[1…i]中的元素进行比较。若发现 A[x]>=K,则将 K ...
### 数据结构中几种常用的排序算法总结 #### 一、引言 在计算机科学与数学领域，排序算法是一种能够按照特定顺序（如数值顺序或字典顺序）排列一系列数据的算法。排序算法对于许多其他算法（如搜索算法和合并算法）...
排序算法总结
常用排序算法总结 数据结构 ppt 课件知识 排序的复杂性 。
### 几种内部排序算法总结 #### 冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，依次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，...
【排序算法总结】 排序算法是计算机科学中一个基础且重要的概念，它用于组织和整理数据，使其按照特定的标准（如升序或降序）排列。本文将深入探讨三种常见的排序算法：选择排序、直接插入排序和冒泡排序。 1. **...
常用排序算法总结，包括插入排序(InsertionSort)，冒泡排序(BubbleSort)，选择排序(SelectionSort)，快速排序（QuickSort)， * 二路归并排序(MergeSort)，堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现...
【排序算法总结】 排序算法是计算机科学中一种重要的算法，主要任务是对一组数据进行排列，使其按照特定的顺序呈现。本文将重点介绍几种基础的排序算法，包括它们的工作原理、性能特点以及适用场景。 1、**稳定度*...