首页 / 算法 / 八大经典排序算法的代码实现

八大经典排序算法的代码实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了八大经典排序算法的代码实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7029字，纯文字阅读大概需要11分钟。

内容图文

冒泡排序：

技术分享图片 技术分享图片 
                 1
                //
                冒泡排序

                 2
                //
                时间复杂度为O(N^2)，空间复杂度为O（N）
                 3
                public
                class
                 BubbleSort {

                 4
                public
                static
                void bubbleSort(int[] arr) {
 5if (arr.length == 0 || arr.length == 1) {
 6return;
 7         } else {
 8//            随着每轮比较的进行，都有一个大数沉到后面排好序，因此外层的循环长度应该递减 9for (int end = arr.length - 1; end > 0; end--) {
10for (int i = 0; i < end; i++) {
11if (arr[i] > arr[i + 1]) {
12                         swap(arr, i, i + 1);
13                    }
14                }
15            }
16        }
1718    }
1920staticvoid swap(int[] arr, int i, int j) {
21//        不利用第三个变量交换两变量的位置。1.a和同一个数异或运算两次得到a本身 2.异或运算满足交换律22         arr[j] = arr[j] ^ arr[i];
23         arr[i] = arr[j] ^ arr[i];
24         arr[j] = arr[j] ^ arr[i];
25    }
2627publicstaticvoid main(String[] args) {
28int[] a = {2, 1, 7, 10, 3, 9, 5, 4, 6, 8};
29        bubbleSort(a);
30for(int i:a)
31             System.out.print(i+",");
32    }
33 }
冒泡排序

插入排序：

技术分享图片 技术分享图片 
                 1
                //
                插入排序

                 2
                //
                复杂度和数据状况有关系，如果本来数组的有序性就比较好则复杂度低
                 3
                public
                class
                 InsertSort {

                 4
                public
                static
                void insertSort(int[] arr) {
 5if (arr == null || arr.length < 2) {
 6return;
 7         } else {
 8for (int i = 1; i < arr.length; i++) {
 9//如果数组的有序性比较好，如1，2，3，4，5，则arr[j + 1] < arr[j]这个条件可以使得比较提前终止，
10//如果数组刚好是逆序的，如5，4，3，2，1，则需要从j一直比较到i=0；11for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--) {
12                     swap(arr, j, j + 1);
13                }
14            }
15        }
16    }
1718staticvoid swap(int[] arr, int i, int j) {
19         arr[j] = arr[j] ^ arr[i];
20         arr[i] = arr[j] ^ arr[i];
21         arr[j] = arr[j] ^ arr[i];
22    }
2324publicstaticvoid main(String[] args) {
25int[] a = {2, 1, 7, 10, 3, 9, 5, 4, 6, 8};
26        insertSort(a);
27for (int i : a)
28             System.out.print(i + ",");
29    }
30 }
插入排序

选择排序：

技术分享图片 技术分享图片 
                 1
                //
                选择排序

                 2
                //
                时间复杂度为O(N^2),空间复杂度为O(1)
                 3
                public
                class
                 SelectionSort {

                 4
                public
                static
                void selectionSort(int[] arr) {
 5if (arr == null || arr.length < 2) {
 6return;
 7         } else {
 8//            每轮都从未排序的数列中取出一个数，将其与后面所有未排序的数作比较，得到这些未排序数列里面的最小数，将它换到已排好序数列的后面，并扩大已排好序数列的范围。 9for (int i = 0; i < arr.length - 1; i++) {
10int minIndex = i;
11//                i = 0作为第一个已排序列12for (int j = i + 1; j < arr.length; j++) {
13                     minIndex = arr[j] < arr[minIndex] ? j : minIndex;
14                }
15                swap(arr, i, minIndex);
16            }
17        }
18    }
1920staticvoid swap(int[] arr, int i, int j) {
21//        此处不能用异或来完成交换，因为如果i=j, 两个相同的数异或等于0，“arr[j] = arr[j] ^ arr[i]”会将arr[i]和arr[j]同时置为0，这样就丢失了所有信息。
22//        如果i和j不相等，但a[i]==a[j]是可以完成异或交换功能的，因为0和任何数异或等于其本身
23//        arr[j] = arr[j] ^ arr[i];
24//        arr[i] = arr[j] ^ arr[i];
25//        arr[j] = arr[j] ^ arr[i];26int tmp = arr[i];
27         arr[i] = arr[j];
28         arr[j] = tmp;
29    }
3031publicstaticvoid main(String[] args) {
32int[] a = {2, 1, 7, 10, 3, 9, 5, 4, 6, 8};
33        selectionSort(a);
34for (int i : a)
35             System.out.print(i + ",");
36    }
37 }
选择排序

归并排序：

技术分享图片 技术分享图片 
                 1
                //
                归并排序

                 2
                //
                时间复杂度O（NlogN）,空间复杂度O（N）

                 3
                //
                分治+外排的方法
                 4
                public
                class
                 MergeSort {

                 5
                public
                static
                void mergeSort(int[] arr) {
 6if (arr == null || arr.length < 2)
 7return;
 8else 9             sortProcess(arr, 0, arr.length - 1);
10    }
1112privatestaticvoid sortProcess(int[] arr, int L, int R) {
13if (L == R)
14return;
15else {
16int mid = L + ((R - L) >> 1);
17//            根据Master公式求其时间复杂度：18             sortProcess(arr, L, mid);//T(N/2)19             sortProcess(arr, mid + 1, R);//T(N/2)20             merge(arr, L, mid, R);//O(N)
21//            根据Master公式，其时间复杂度为T(N) = 2T(N/2)+O(N) = N*logN22        }
23    }
2425//融合两个有序数组，使之成为一个更大的有序数组的方法，叫做外排26privatestaticvoid merge(int[] arr, int l, int mid, int r) {
27//        空间复杂度O(体现在需要一个大小为数据量N的辅助数组help上)28int[] help = newint[r - l + 1];
29int i = 0;
30int p1 = l;
31int p2 = mid + 1;
32while (p1 <= mid && p2 <= r)
33             help[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
34//        两个必有且只有一个越界35while(p1<=mid)
36             help[i++] = arr[p1++];
37while(p2<=r)
38             help[i++] = arr[p2++];
3940         i = 0;
41while(l<=r)
42             arr[l++] = help[i++];
43    }
4445publicstaticvoid main(String[] args) {
46int[] a = {2, 1, 7, 10, 3, 9, 5, 4, 6, 8};
47        mergeSort(a);
48for(int i:a)
49             System.out.print(i+",");
50    }
51 }
View Code

快速排序:

技术分享图片 技术分享图片 
                 1
                import
                 java.util.Arrays;

                 2
                 3
                //
                快排

                 4
                //
                时间复杂度最好为O(NlogN). 数组逆序的时候最差，时间复杂度为O(N^2),可以通过随机快排的方式使得其长期时间复杂度期望为O（N*logN）

                 5
                //
                空间复杂度最好为O（logN）,数组逆序的时候最差，空间复杂度为O(N)，额外空间主要是每次partition函数返回的二元数组造成的。

                 6
                //
                通过随机快排的方式使得其长期时间复杂度期望为O（logN）

                 7
                //
                所有递归函数都可以改为非递归版本，因为递归的本质行为是系统在帮我们压栈。改为非递归就是改成我们自己来压栈

                 8
                //
                 在工程上是不允许递归行为存在的，因为递归过深可能会导致系统栈爆满，系统不稳定。因此工程上的快排都是非递归版本实现的。

                 9
                //
                库函数都是高度优化过的
                10
                public
                class
                 QuickSort {

                11
                12
                static
                void quickSort(int[] arr, int L, int R) {
13if (L < R) {
14//            随机快排， 每次将中间随机一个数和数列最后一个元素交换位置，放置逆序数列产生差的结果15             swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
16int[] p = partition(arr, L, R);
17             quickSort(arr, L, p[0] - 1);
18             quickSort(arr, p[1] + 1, R);
19        }
20    }
2122staticint[] partition(int[] arr, int L, int R) {
23int less = L - 1;
24int more = R;
25int cur = L;
26//        以arr[R]作为基准，有了随机快排，这里的arr[R]被重新洗牌
27//        这里一次性处理了大于基准等于基准和小于基准的三种情况，速度比传统快排要快28while (cur < more) {
29if (arr[cur] < arr[R]) {
30// cur++,因为换到cur位置上的一定是比基准arr[R]小的数，直接将其扩到less范围去，且cur指向下一位置31                 swap(arr, ++less, cur++);
32             } elseif (arr[cur] > arr[R]) {
33//交换到cur位置上的数大小位置，交换过去的数一定大于基准arr[R]， 故more--,将其扩到more区域， 但cur位置不变34                 swap(arr, --more, cur);
35             } else {
36//当前位置和基准arr[R]相等，不扩到less区域和more区域，放在相等区域37                 cur++;
38            }
39        }
40//最后将基准交换到more区域的下一位置41        swap(arr, more, R);
42// 返回相等区域下标,注意此时more位置上是交换过来的基准值，不用加143returnnewint[]{less + 1, more};
44    }
4546staticvoid swap(int[] arr, int i, int j) {
47int tmp = arr[i];
48         arr[i] = arr[j];
49         arr[j] = tmp;
50    }
5152publicstaticvoid main(String[] args) {
53int a[] = {49, 38, 65, 97, 76, 13, 27, 49};
54         quickSort(a, 0, a.length - 1);
55        System.out.println(Arrays.toString(a));
56    }
57 }
快排

堆排序：

技术分享图片 技术分享图片 
                 1
                import
                 java.util.Arrays;

                 2
                 3
                //
                堆排序

                 4
                //
                堆是完全二叉树

                 5
                //
                二叉树的底层可以用线性的结构来储存，也就是说可以用数组来储存一个二叉树，通过数组中下标的关系来表示这个堆。设完全二叉树的一个节点在数组中的下标为i,

                 6
                //
                则其父节点的下标应该为(i-1)/2,其左孩子节点应该是2*i+1, 其右孩子节点应该为2*i+2
                 7
                public
                class
                 HeapSort {

                 8
                static
                void heapSort(int[] arr) {
 9if (arr == null || arr.length < 2)
10return;
11else12for (int i = 0; i < arr.length; i++)
13                heapInsert(arr, i);
1415int heapSize = arr.length;//堆的大小等于数组的长度
16//交换堆顶和最后一个元素17         swap(arr, 0, --heapSize);
18while (heapSize > 0) {
19             heapify(arr, 0, heapSize);
20             swap(arr, 0, --heapSize);
21        }
22    }
2324staticvoid heapInsert(int[] arr, int index) {
25while (arr[(index - 1) / 2] < arr[index]) {//如果index=0, -1/2=0是根节点26             swap(arr, index, (index - 1) / 2);
27             index = (index - 1) / 2;
28        }
2930    }
3132//    如果堆中有某个元素变小了，将这个元素下沉以保持大根堆的过程heapify33staticvoid heapify(int[] arr, int index, int heapSize) {
34int left = index * 2 + 1;//在用数组存储的堆中，节点i的左孩子节点是2*i+1, 右节点是2*i+2;
35//这里heapSize是最后一个元素，做堆排的时候，因为是从堆顶交换来的最大值，所以重新heapify要把它排除在外；36while (left < heapSize) {
37int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
38             largest = arr[index] > arr[largest] ? index : largest;
39if (largest == index) {
40break;
41            }
42            swap(arr, largest, index);
43             index = largest;
44             left = index * 2 + 1;
45        }
46    }
4748staticvoid swap(int[] arr, int i, int j) {
49int tmp = arr[i];
50         arr[i] = arr[j];
51         arr[j] = tmp;
52    }
5354publicstaticvoid main(String[] args) {
55int a[] = {49, 38, 65, 97, 76, 13, 27, 49};
56        heapSort(a);
57        System.out.println(Arrays.toString(a));
58    }
59 }
堆排序

希尔排序：

基数排序：

 

原文：https://www.cnblogs.com/greatLong/p/10562405.html

内容总结

以上是互联网集市为您收集整理的八大经典排序算法的代码实现全部内容，希望文章能够帮你解决八大经典排序算法的代码实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1111034.html

来源：【匿名】