🍀排序算法-平均时间复杂度

🍀 O(n2)O(n^2)O(n2)的排序算法

☘️冒泡排序

两个数比较大小，如要求是升序排序，则较大的数往下沉，较小的数往上冒。

伪代码

BubbleSort(A)for i = 1 to A.length-1for j = A.length-1 downto iif A[j] < A[j - 1]exchange A[j] with A[j - 1]

Java版

public int[] BubbleSort(int[] list) {int len = list.length;for (int i = 1; i < len; i++) {for (int j = len - 1; j >= i; j--) {if(list[j] < list[j-1]) {int tmp = list[j];list[j] = list[j-1];list[j-1] = tmp;}}}return list;}

Java泛型版

public <T extends Comparable<T>> T[] BubbleSort(T list[]) {int len = list.length;for (int i = 1; i < len; i++) {for (int j = len - 1; j >= i; j--) {if (list[j].compareTo(list[j - 1]) > 0) {T tmp = list[j];list[j] = list[j - 1];list[j - 1] = tmp;}}}return list;}

1、时间复杂度：O(n2)O(n^2)O(n2)

2、空间复杂度：O(1)O(1)O(1)

3、稳定排序

4、原地排序

☘️选择排序

每次选择最小或者最大的元素排列到有序区。

在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；

第二次遍历n-2个数，找到最小的数值与第二个元素交换；

重复。。。

第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

伪代码

SelectionSort(A)for i=1 to A.length-1min=i for j=i+1 to A.lengthif A[j]<A[min]min=jtem=A[min]A[min]=A[i]A[i]=tem

Java版

public int[] SelectionSort(int[] list) {int len = list.length, minT;for (int i = 0; i < len; i++) {minT = i;for (int j = i + 1; j < len; j++) {if (list[j] <list[minT]) {minT = i;}}int tmp = list[minT];list[minT] = list[i];list[i] = tmp;}return list;}

Java泛型版

public <T extends Comparable<T>> T[] SelectionSort(T[] list) {int len = list.length, minT;for (int i = 0; i < len; i++) {minT = i;for (int j = i + 1; j < len; j++) {if (list[j].compareTo(list[minT]) < 0) {minT = i;}}T tmp = list[minT];list[minT] = list[i];list[i] = tmp;}return list;}

1、时间复杂度：O(n2)O(n^2)O(n2)

2、空间复杂度：O(1)O(1)O(1)

3、非稳定排序

4、原地排序

☘️插入排序

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

伪代码

InsertionSort(A)for j = 2 to A.lengthkey = A[j]i = j-1while i > 0 and A[i] > keyA[i+1] = A[i]i = i -1A[i+1] = key

Java代码

public int[] InsertionSort(int list[]) {int len = list.length;for (int i = 1; i < len; i++) {int tmp = list[i];int j = i - 1;// 将比插入元素值大的数往后移动while (j >= 0 && list[j] > tmp) {list[j + 1] = list[j];j--;}// 插入元素list[j + 1] = tmp;}return list;}

Java泛型版

public <T extends Comparable<T>> T[] InsertionSort(T list[]) {int len = list.length;for (int i = 1; i < len; i++) {T tmp = list[i];int j = i - 1;// 将比插入元素值大的数往后移动while (j >= 0 && list[j].compareTo(tmp) > 0) {list[j + 1] = list[j];j--;}// 插入元素list[j + 1] = tmp;}return list;}

1、时间复杂度：O(n2)O(n^2)O(n2)

2、空间复杂度：O(1)O(1)O(1)

3、稳定排序

4、原地排序

🍀 O(n∗logN)O(n*logN)O(n∗logN)的排序算法

☘️希尔排序

在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。

然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

假如待排序数组基本有序，使用插入排序更有效。

伪代码

ShellSort(A)d=A.lengthdod = d/2for i = 1 to A.length - dj = i + dif(A[i] > A[j]exchange A[i] and A[j]while(d>1)

Java代码

public int[] ShellSort(int list[]) {int len = list.length;int d = len;do {d /= 2;for (int i = 0; i < len - d; i++) {int j = i + d;if (list[j] < list[i]) {int tmp = list[i];list[i] = list[j];list[j] = tmp;}}} while (d > 1);return list;}

Java泛型版

public <T extends Comparable<T>> T[] ShellSort(T list[]) {int len = list.length;int d = len;do {d /= 2;for (int i = 0; i < len - d; i++) {int j = i + d;if (list[j].compareTo(list[i]) < 0) {T tmp = list[i];list[i] = list[j];list[j] = tmp;}}} while (d > 1);return list;}

1、时间复杂度：O(nlogN)O(nlogN)O(nlogN) - O(n2)O(n^2)O(n2)，平均为O(n1.5)O(n^{1.5})O(n1.5)

2、空间复杂度：O(1)

3、非稳定排序

4、原地排序

☘️归并排序

归并算法是分治思想一个经典应用。

将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。

归并排序的分治思想

分解：分解待排序的n个元素的序列成各具 n/2 个元素的子序列解决：使用归并排序递归地排序子序列合并：合并两个已经排序的子序列以产生已排序的答案。

伪代码

Merge(A, p, q, r)n1 = q-p+1n2 = r-q//let L[1....n1+1] and R[1....n2+1] be new arraysfor i =1 to n1L[i] = A[p+i-1]for j=1 to n2R[j] = A[q+j]L[n1+1] = ∞L[n2+1] = ∞i=1j=1for k =p to rif L[i]<=R[j]A[k] = L[i]i = i + 1elseA[k]=R[j]j = j+1MergeSort(A,p,r)if p < rq = ⌊(p+r)/2⌋ //向下取整MergeSort(A, p, q)MergeSort(A, q+1, r)Merge(A, p, q, r)

Java代码

public int[] MergeSort(int list[]) {int tmp[] = new int[list.length]; //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间MergeSort(list, 0, list.length - 1, tmp);return list;}public void MergeSort(int[] list, int l, int r, int tmp[]) {if (l < r) {int mid = (l + r) / 2;MergeSort(list, l, mid, tmp);MergeSort(list, mid + 1, r, tmp);Merge(list, l, mid, r, tmp);}}void Merge(int list[], int l, int mid, int r, int tmp[]) {int i = l; //左序列指针int j = mid + 1; //右序列指针int t = 0; //临时数组指针while (i <= mid && j <= r) {if (list[i] <= list[j]) {tmp[t++] = list[i++];} else {tmp[t++] = list[j++];}}while (i <= mid) {//将左边剩余元素填充进temp中tmp[t++] = list[i++];}while (j <= r) {//将右序列剩余元素填充进temp中tmp[t++] = list[j++];}t = 0;//将temp中的元素全部拷贝到原数组中while (l <= r) {list[l++] = tmp[t++];}}

1、时间复杂度：O(nlogN)O(nlogN)O(nlogN)

2、空间复杂度：O(n)O(n)O(n)

3、稳定排序

4、非原地排序

☘️堆排序

堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。

建立大顶堆；

拿掉堆顶的元素，重新构建堆；

拿掉堆顶元素，重新构建堆。。。

等到堆剩余的元素只有一个的时候，此时的数组就是有序的了。

伪代码

HeapSort(A)BuildMaxHeap(A)for i = A.length downto 2exchange A[1] with A[i]A.heap-size = A.heap-size - 1MaxHeapify(A, 1)// 建立大顶堆BuildMaxHeap(A)A.heap-size = A.lengthfor i = int(A.length / 2) downto 1MaxHeapify(A, i)//维护堆MaxHeapify(A, i)l = LEFT(i)r = RIGHT(i)if l <= A.heap-size and A[l] > A[i]largest = lelse largest = iif r <= A.heap-size and A[r] > A[largest]largest = rif largest <> iexchange A[i] with A[largest]MaxHeapify(A, largest)

Java代码

public int[] HeapSort(int list[]) {BuildMaxHeap(list);for (int i = list.length - 1; i >= 0; i--) {int tmp = list[0];list[0] = list[i];list[i] = tmp;MaxHeapify(list, 0, i);}return list;}public void BuildMaxHeap(int list[]) {// 构建大顶堆int heapSize = list.length;for (int i = (heapSize / 2); i >= 0; i--) {MaxHeapify(list, i, heapSize);}}public void MaxHeapify(int list[], int i, int heapSize) {// 维护堆int l = LEFT(i);int r = RIGHT(i);int largest;if (l <= heapSize - 1 && list[l] > list[i]) {largest = l;} else {largest = i;}if (r <= heapSize - 1 && list[r] > list[largest]) {largest = r;}if (largest != i) {int tmp = list[i];list[i] = list[largest];list[largest] = tmp;MaxHeapify(list, largest, heapSize);}}public int PARENT(int i) {return (i - 1) / 2;}public int LEFT(int i) {return 2 * i + 1;}public int RIGHT(int i) {return 2 * i + 2;}

1、时间复杂度：O(nlogN)O(nlogN)O(nlogN)

2、空间复杂度：O(1)O(1)O(1)

3、非稳定排序

4、原地排序

☘️快速排序

同样是分治思想。

先从数列中取出一个数作为key值；

将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；

对左右两个小数列重复第二步，直至各区间只有1个数。

伪代码

QuickSort(A, p, r)if p < rq = Partition(A,p,r）QuickSort(A,p,q-1)QuickSort(A,q+1,r)Partition(A, p, r)x = A[r]i = p-1for j = p to r-1if A[j] <= x //<=与书上有区别，符号的区别，不会打那个。。。。i = i + 1exchange A[i] with A[j]exchange A[i+1] with A[r]return i + 1

Java代码

public int[] QuickSort(int list[]) {QuickSort(list, 0, list.length - 1);return list;}public void QuickSort(int list[], int l, int r) {if (l < r) {int mid = Partition(list, l, r);QuickSort(list, l, mid - 1);QuickSort(list, mid + 1, r);}}public int Partition(int list[], int l, int r) {int x = list[r];int i = l - 1;for (int j = l; j <= r - 1; j++) {if (list[j] <= x) {i = i + 1;int tmp = list[i];list[i] = list[j];list[j] = tmp;}}int tmp = list[i + 1];list[i + 1] = list[r];list[r] = tmp;return i + 1;}

1、时间复杂度：O(nlogN)O(nlogN)O(nlogN)

2、空间复杂度：O(logN)O(logN)O(logN)

3、非稳定排序

4、原地排序

🍀O(n+k)O(n+k)O(n+k)的排序算法、非比较排序

☘️计数排序

把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = n, 表示元素 i 一共出现了 n 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

计数排序比较适用于待排序数组中最大值和最小值相差不大的排序。

伪代码

CountingSort(A,B,k)let C[0..k] be a new arrayfor i = 0 to k //后面需要使用数组C来存储A中各元素的出现次数，所以需要清零操作C[i] = 0for j = 1 to A.length C[A[j]] = C[A[j]] + 1 //统计A中各元素的出现次数存储在C中，C中下标为A中的元素值，与其对应的数组元素为出现次数，如C[1] = 0，即为“1”在A中的出现次数为0for i = 1 to k C[i] = C[i] + C[i-1] //计算A中小于等于i的一共有多少个，方便此后将i放在数组B中正确的位置上for j = A.length downto 1B[C[A[j]]] = A[j] //使用A中元素A[j]的出现次数作为B中的下标，把每个元素放在B中适当的位置C[A[j]] = C[A[j]] -1 //在B中放入一个元素，与其对应C中出现的次数-1。这样，当遇到下一个等于A[j]的输入元素时，该元素可以被直接放到B中A[j]的前一位置上

Java代码

public int[] CountingSort(int list[]) {int maxNum = Arrays.stream(list).max().getAsInt();CountingSort(list, maxNum);return list;}public void CountingSort(int list[], int maxNum) {int tmp[] = new int[maxNum + 1];int res[] = new int[list.length];for (int item : list) {tmp[item]++;}for (int i = 1; i < tmp.length; i++) {tmp[i] += tmp[i - 1];}for (int i = list.length - 1; i >= 0; i--) {// 数组下标从0开始，此处减1res[tmp[list[i]]-1] = list[i];tmp[list[i]]--;}}

1、时间复杂度：O(n+k)O(n+k)O(n+k) ，K：建立的计数数组长度

2、空间复杂度：O(n+k)O(n+k)O(n+k)

3、稳定排序

4、非原地排序

☘️基数排序

先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小。。。

排到最后，就是一组有序的元素了。

伪代码

RADIXSORT(A,d) // d:最高位数for i = 1 to duse a stable sort to sort array A on digit i // 从个位数至高位数依次重复排序

Java代码

public int[] RadixSort(int list[]) {int maxNum = Arrays.stream(list).max().getAsInt();int d = 0;while(maxNum!=0) {maxNum /=10;d++;}RadixSort(list,d);return list;}public void RadixSort(int list[], int d) {int[] res = new int[list.length];//结果数组int[] tmp = new int[10];//计数数组，范围为每位上的取值范围0-9//一个十进制数m，它的个位数是m/1%10，十位数是m/10%10,百位数是m/100%10for(int i=0;i<d;i++) {int division = (int)Math.pow(10, i);//取个位::/1 十位:/10 百位:/100中的基本划分点for(int j=0;j<list.length;j++) {int num = list[j]/division%10;//取个位 十位 或百位上的数，每轮由此位置上的数大小进行计数排序tmp[num]=tmp[num]+1;//进行计数排序中计数数组的更新}//计数排序中计数数组count的累加，保证稳定性for(int m=1;m<tmp.length;m++) {tmp[m]=tmp[m]+tmp[m-1];}//计数排序中逆序遍历原数组A，根据累加后的数组count将A中每个元素正确填入result中正确的位置中for(int j=list.length-1;j>=0;j--) {int num = list[j]/division%10;res[tmp[num]-1]=list[j];tmp[num]=tmp[num]-1;}//将数组A更新为数组Bfor(int j=0;j<list.length;j++) {list[j]=res[j];}//将数组C清零，进行下一轮的循环for(int j=0;j<tmp.length;j++) {tmp[j]=0;}}}

1、时间复杂度：O(n+k)O(n+k)O(n+k) ，K：建立的计数数组长度

2、空间复杂度：O(n+k)O(n+k)O(n+k)

3、稳定排序

4、非原地排序

☘️桶排序

把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，对桶中元素排序可采用其他排序方法。每个桶排序后再合并起来形成有序数组。

伪代码

BucketSort(A)n = A.lengthlet B[0...n-1] be a new arrayfor i = 0 to n-1b[i]=0//make B an empty listfor i =1 to ninsert A[i] into list B[(int)nA[i]]for i =0 to n-1sort list B[i] with insertion sortconcatenate hte lists B[0...n-1] together in order

Java代码

class LinkedNode {public int value;public LinkedNode next;public LinkedNode(int value) {this.value = value;}}public int[] BucketSort(int list[]) {int length = list.length;LinkedNode[] bucket = new LinkedNode[length]; // 桶的个数等于lengthint max = list[0]; // 求maxfor (int i = 1; i < list.length; i++) {if (list[i] > max) {max = list[i];}}// 入桶for (int i = 0; i < length; i++) {int value = list[i]; // 扫描每个元素int hash = hash(list[i], max, length); // 桶的下标if (bucket[hash] == null) {bucket[hash] = new LinkedNode(value); // 初始化链表} else {insertInto(value, bucket[hash], bucket, hash); // 插入链表}}int k = 0; // 记录数组下标// 出桶，回填arrfor (LinkedNode node : bucket) {if (node != null) {while (node != null) {list[k++] = node.value;node = node.next;}}}return list;}private int hash(int element, int max, int length) {return (element * length) / (max + 1);}private void insertInto(int value, LinkedNode head, LinkedNode[] bucket, int hash) {LinkedNode newNode = new LinkedNode(value);// 小于头节点，放在头上if (value <= head.value) {newNode.next = head;// 替换头节点bucket[hash] = newNode;return;}// 往后找第一个比当前值大的节点，放在这个节点的前面LinkedNode p = head;LinkedNode pre = p;while (p != null && value > p.value) {pre = p;p = p.next;}if (p == null) {// 跑到末尾了pre.next = newNode;} else {// 插入pre和p之间pre.next = newNode;newNode.next = p;}}

1、时间复杂度：O(n+k)O(n+k)O(n+k) ，K：建立的计数数组长度

2、空间复杂度：O(n+k)O(n+k)O(n+k)

3、稳定排序

4、非原地排序

排序算法理解总结篇——冒泡排序 选择排序 插入排序 希尔排序 归并排序 堆排序 计数排序 基数排序 桶排序