算法基础

ゝ一世哀愁。 2022-12-16 06:07 146阅读 0赞

# 排序算法 #

## 1.冒泡排序 ##

public static void sort(int[] arr) {
        
            for (int i = 0; i < arr.length - 1; i++) {
        
                for (int j = 0; j < arr.length - 1 - i; j++) {
        
                    if (arr[j] > arr[j + 1]) {
        
                        int tmp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = tmp;
                    }
                }
            }
        }

## 2.选择排序 ##

public static void sort(int[] arr) {
        
            for (int i = 0; i < arr.length; i++) {
        
                int min = i;
                for (int j = i + 1; j < arr.length; j++) {
        
                    if (arr[j] < arr[min]) min = j;
                }
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }

## 3.插入排序 ##

public static void sort(int[] arr) {
        
            for (int i = 1; i < arr.length; i++) {
        
                int val = arr[i];
                int j = 0;
                for (j = i - 1; j >= 0; j--) {
        
                    if (arr[j] > val) arr[j + 1] = arr[j];
                    else break;
                }
                arr[j + 1] = val;
            }
        }

## 4.希尔排序 ##

public static void sort(int[] arr) {
        
            int gap = 1;
            while (gap < arr.length) {
        
                gap = gap * 3 + 1;
            }
            while (gap > 0) {
        
                for (int i = gap; i < arr.length; i++) {
        
                    int val = arr[i];
                    int j = i - gap;
                    while (j >= 0 && arr[j] > val) {
        
                        arr[j + gap] = arr[j];
                        j -= gap;
                    }
                    arr[j + gap] = val;
                }
                gap = gap / 3;
            }
        }

## 5.归并排序 ##

public static void sort(int[] arr) {
        
            int[] tmpArr = new int[arr.length];
            sort(tmpArr, arr, 0, arr.length - 1);
        }
    
        private static void sort(int[] tmpArr, int[] arr, int startIndex, int endIndex) {
        
            if (startIndex >= endIndex) return;
            int midIndex = startIndex + (endIndex - startIndex) / 2;
            sort(tmpArr, arr, startIndex, midIndex);
            sort(tmpArr, arr, midIndex + 1, endIndex);
            merge(tmpArr, arr, startIndex, midIndex, endIndex);
        }
    
        private static void merge(int[] tmpArr, int[] arr, int startIndex, int midIndex, int endIndex) {
        
            for (int i = startIndex; i <= endIndex; i++) {
        
               tmpArr[i] = arr[i];
            }
            int left = startIndex, right = midIndex + 1;
            for (int j = startIndex; j <= endIndex; j++) {
        
                if (left > midIndex) arr[j] = tmpArr[right++];
                else if (right > endIndex) arr[j] = tmpArr[left++];
                else if (tmpArr[right] < tmpArr[left]) arr[j] = tmpArr[right++];
                else arr[j] = tmpArr[left++];
            }
        }

## 6.快排 ##

public static void sort(int[] arr) {
        
            sort(arr, 0, arr.length - 1);
        }
    
        private static void sort(int[] arr, int startIndex, int endIndex) {
        
            if (startIndex >= endIndex) return;
            int pivotIndex = partation(arr, startIndex, endIndex);
            sort(arr, startIndex, pivotIndex - 1);
            sort(arr, pivotIndex + 1, endIndex);
        }
    
        private static int partation(int[] arr, int startInex, int endIndex) {
        
            int pivot = arr[startInex];
            int mark = startInex;
            for (int i = startInex + 1; i <= endIndex; i++) {
        
                if (arr[i] < pivot) {
        
                    mark++;
                    int p = arr[mark];
                    arr[mark] = arr[i];
                    arr[i] = p;
                }
            }
            arr[startInex] = arr[mark];
            arr[mark] = pivot;
            return mark;
        }

## 7.堆排 ##

public static void sort(int[] arr) {
        
            int len = arr.length;
            buildHeap(arr, len);
            for (int i = len - 1; i > 0; i--) {
        
                int tmp = arr[0];
                arr[0] = arr[i];
                arr[i] = tmp;
                len--;
                sink(arr, 0, len);
            }
        }
    
        private static void buildHeap(int[] arr, int len) {
        
            for (int i = len / 2; i >= 0; i--) {
        
                sink(arr, i, len);
            }
        }
    
        private static void sink(int[] arr, int index, int len) {
        
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int present = index;
    
            if (leftChild < len && arr[leftChild] > arr[present]) present = leftChild;
            if (rightChild < len && arr[rightChild] > arr[present]) present = rightChild;
            if (present != index) {
        
                int tmp = arr[index];
                arr[index] = arr[present];
                arr[present] = tmp;
                sink(arr, present, len);
            }
        }

## 8.计数排序 ##

public static void sort(int[] arr) {
        
            int max = arr[0];
            for (int i = 1; i < arr.length; i++) {
        
                if (arr[i] > max) max = arr[i];
            }
            int[] countArr = new int[max + 1];
            for (int i = 0; i < arr.length; i++) {
        
                countArr[arr[i]]++;
                arr[i] = 0;
            }
            int index = 0;
            for (int i = 0; i < countArr.length; i++) {
        
                if (countArr[i] > 0) arr[index++] = i;
            }
        }

## 9.桶排序 ##

public static void sort(int[] arr) {
        
    
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < arr.length; i++){
        
                max = Math.max(max, arr[i]);
                min = Math.min(min, arr[i]);
            }
    
            int bucketNum = (max - min) / arr.length + 1;
            ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
            for(int i = 0; i < bucketNum; i++){
        
                bucketArr.add(new ArrayList<Integer>());
            }
    
            for(int i = 0; i < arr.length; i++){
        
                int num = (arr[i] - min) / (arr.length);
                bucketArr.get(num).add(arr[i]);
            }
    
            for(int i = 0; i < bucketArr.size(); i++){
        
                Collections.sort(bucketArr.get(i));
            }
    
            int index = 0;
            for(ArrayList<Integer> arrayList : bucketArr){
        
                for(int value : arrayList){
        
                    arr[index] = value;
                    index++;
                }
            }
        }

## 10.基数排序 ##

public static void sort(int[] arr) {
        
            int len = arr.length;
            int max = arr[0];
            for (int i = 0; i < len; i++) {
        
                if (arr[i] > max) max = arr[i];
            }
            int location = 1;
            ArrayList<ArrayList<Integer>> buckList = new ArrayList<>();
            for (int i = 0; i < 10; i++) {
        
                buckList.add(new ArrayList());
            }
            while(true) {
        
                int dd = (int)Math.pow(10, (location - 1));
                if (max < dd) break;
                for (int i = 0; i < len; i++) {
        
                    int number = ((arr[i] / dd) % 10);
                    buckList.get(number).add(arr[i]);
                }
                int nn = 0;
                for (int i = 0; i < 10; i++) {
        
                    int size = buckList.get(i).size();
                    for (int ii = 0; ii < size; ii++) {
        
                        arr[nn++] = buckList.get(i).get(ii);
                    }
                    buckList.get(i).clear();
                }
                location++;
            }
        }