排序算法
前言
排序算法有很多，这里只列举了常见的几种基础算法如：冒泡排序、插入排序、选择排序、快速排序。对算法感兴趣的可以去LeeCode里面深度学习哦。
冒泡排序
private static void Swap(int[] nums,int i,int j){
int val=nums[i];
nums[i]=nums[j];
nums[j]=val;
}
/*
冒泡排序：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
*/
public static void BubbleSort(int[] nums){
for(int i=nums.length-1;i>0;i--){ //外层循环控制排序的轮数
boolean isSorted=true;
for(int j=0;j<i;j++){ //内层循环每次将未排序序列中最大的数冒泡到最后端
if(nums[j]>nums[j+1]){
Swap(nums,j,j+1);
isSorted=false;
}
}
if(isSorted) break;
}
}
选择排序
private static void Swap(int[] nums,int i,int j){
int val=nums[i];
nums[i]=nums[j];
nums[j]=val;
}
/*
选择排序：
1.第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置
2.然后再从剩余的未排序元素中寻找到最小（大）元素，放到已排序的序列的末尾
3.以此类推，直到全部待排序的数据元素的个数为零
*/
public static void SelectSort(int[] nums){
for(int i=0;i<nums.length;i++){
int index=i;
for(int j=i+1;j<nums.length;j++){
if(nums[j]<nums[index]) index=j;
}
Swap(nums,i,index);
}
}
插入排序
/*
插入排序：
基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，
内层循环对当前元素前面有序表进行待插入位置查找，并进行移动
*/
public static void InsertSort(int[] nums){
for(int i=1;i<nums.length;i++){
int val=nums[i];
int j=i;
while(j>0&&nums[j-1]>val){
nums[j]=nums[j-1];
j--;
}
nums[j]=val;
}
}
快速排序
private static void Swap(int[] nums,int i,int j){
int val=nums[i];
nums[i]=nums[j];
nums[j]=val;
}
/*
快速排序：
1.首先设定一个分界值，通过该分界值将数组分成左右两部分。
2.将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
*/
public static void FastSort(int[] nums,int start,int end) {
if(start>=end) return ;
int val=nums[start];
int i=start,j=end;
while (i<j){
// 顺序很重要，先从右边开始往左找，直到找到比base值小的数
while(nums[j] >= val && i < j) {
j--;
}
// 再从左往右边找，直到找到比base值大的数
while(nums[i] <= val && i < j) {
i++;
}
if(i<j&&nums[i]>nums[j]){
Swap(nums,i,j);
}
}
nums[start]=nums[i];
nums[i]=val;
FastSort(nums,start,i-1);
FastSort(nums,i+1,end);
}
总结
这里贴上部分排序时间复杂度：
在贴上所有代码：
public class SortMethod {
private static void Swap(int[] nums, int i, int j) {
int val = nums[i];
nums[i] = nums[j];
nums[j] = val;
}
/*
选择排序：
1.第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置
2.然后再从剩余的未排序元素中寻找到最小（大）元素，放到已排序的序列的末尾
3.以此类推，直到全部待排序的数据元素的个数为零
*/
public static void SelectSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int index = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[index]) index = j;
}
Swap(nums, i, index);
}
}
/*
冒泡排序：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
*/
public static void BubbleSort(int[] nums) {
for (int i = nums.length - 1; i > 0; i--) { //外层循环控制排序的轮数
boolean isSorted = true;
for (int j = 0; j < i; j++) { //内层循环每次将未排序序列中最大的数冒泡到最后端
if (nums[j] > nums[j + 1]) {
Swap(nums, j, j + 1);
isSorted = false;
}
}
if (isSorted) break;
}
}
/*
插入排序：
基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，
内层循环对当前元素前面有序表进行待插入位置查找，并进行移动
*/
public static void InsertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int val = nums[i];
int j = i;
while (j > 0 && nums[j - 1] > val) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = val;
}
}
/*
快速排序：
1.首先设定一个分界值，通过该分界值将数组分成左右两部分。
2.将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
*/
public static void FastSort(int[] nums, int start, int end) {
if (start >= end) return;
int val = nums[start];
int i = start, j = end;
while (i < j) {
// 顺序很重要，先从右边开始往左找，直到找到比base值小的数
while (nums[j] >= val && i < j) {
j--;
}
// 再从左往右边找，直到找到比base值大的数
while (nums[i] <= val && i < j) {
i++;
}
if (i < j && nums[i] > nums[j]) {
Swap(nums, i, j);
}
}
nums[start] = nums[i];
nums[i] = val;
FastSort(nums, start, i - 1);
FastSort(nums, i + 1, end);
}
}