常见排序算法总结

拼搏现实的明天。 2022-12-02 14:00 146阅读 0赞

1.  冒泡排序

/** * 重复地走访要排序的元素，一次比较相邻两个元素，如果他们是逆序就把他们调换过来，直到没有元素再需要交换，排序完成。 * * @param nums */
        public static void bubbleSort(int[] nums){ 
            int len = nums.length;
            boolean flag = false;
            for(int i=0;i<len;i++){ 
                flag = false;
                for(int j =1;j<len-i;j++){ 
                    if(nums[j-1] > nums[j]){ 
                        int tmp = nums[j-1];
                        nums[j-1]= nums[j];
                        nums[j] = tmp;
                    }
                }
                if(flag){ 
                    break;
                }
            }
        }

1.  选择排序

/** * 选择排序类似于冒泡排序，选择排序是首先在未排序的序列中找到最小值（最大值），放到序列的末尾位置，然后再从剩余未排序元素中继续寻找最小（大）元素 * 放到已排序序列的开始，以此类推，直到所有元素均排序完毕。 * @param nums */
        public static  void  selectSort(int [] nums){ 
            int len = nums.length;
            int maxIndex=0;
            for(int i=len-1;i>=0;i--){ 
                maxIndex = 0;
                for(int j=0;j<=i;j++){ 
                  if(nums[j]>nums[maxIndex]){ 
                      maxIndex = j;
                  }
                }
                int tmp =  nums[i];
                nums[i] = nums[maxIndex];
                nums[maxIndex] = tmp;
            }
        }

1.  插入排序

/** * 首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。 * * 时间复杂度：O(n^2)，最优时间复杂度：O(n^2),平均时间复杂度：O(n^2) * @param nums */
        public  static void insertionSort(int [] nums){ 
            int len = nums.length;
            int tmp;
            int j;
            for(int i=1;i<len;i++){ 
                tmp = nums[i];
                for( j=i;j>0 && nums[j-1] > tmp;j--){ 
                    nums[j] = nums[j-1];
                }
                nums[j] = tmp;
            }
        }

1.  快速排序

/** * 从数列中挑出一个元素，称为"基准"（pivot）， * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 * @param nums * @param l * @param r */
        public static void quickSort(int[] nums,int l,int r){ 
            if(l<r){ 
                int i,j,x;
                i = l;
                j = r;
                x= nums[i];
                while (i<j){ 
                    while (i<j&&nums[j]>x);{ 
                        j--;
                    }
                    if(i<j){ 
                        nums[i++] = nums[j];
                    }
                    while (i<j && nums[i]<x){ 
                        i++;
                    }
                    if(i<j){ 
                        nums[j--] = nums[i];
                    }
                }
                nums[i] = x;
                quickSort(nums,l,i-1);
                quickSort(nums,i+1,r);
            }
        }

1.  堆排序

/** 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算 */
    public static void headSort(int[] nums){ 
            for(int i = nums.length/2;i>=0;i--){ 
                heapAdjust(nums,i,nums.length);
            }
    
            for(int i=nums.length-1,temp=0;i>0;i--){ 
                temp = nums[i];
                nums[i] = nums[0];
                nums[0] = temp;
                heapAdjust(nums,0,i);
            }
    
        }
    
        private static void heapAdjust(int[] nums, int parent, int len) { 
            int temp = nums[parent];
            int lChild = 2*parent+1;
            while (lChild <len){ 
                if(lChild +1<len && nums[lChild +1 ] > nums[lChild])
                { 
                    lChild ++;
                }
    
                if(nums[parent] > nums[lChild]){ 
                    break;
                }
                nums[parent] = nums[lChild];
                parent = lChild;
                lChild = 2*lChild+1;
            }
            nums[parent] = temp;
        }