数据结构排序算法的java实现

ゞ浴缸里的玫瑰 2022-01-29 05:21 201阅读 0赞

**一、冒泡排序**

public static void bubbleSort(int[] datas) {
    
            int length = datas.length;
            boolean sortFlag = true;
            for (int index = 0; index < length && sortFlag; index++) {
                sortFlag = false;
                for (int compareIndex = 0; compareIndex < length - index - 1; compareIndex++) {
                    if (datas[compareIndex] > datas[compareIndex + 1]) {
                        sortFlag = true;
                        int tempData = datas[compareIndex];
                        datas[compareIndex] = datas[compareIndex + 1];
                        datas[compareIndex + 1] = tempData;
                    }
                }
            }
        }

**二、简单选择排序**

public static void selectSort(int[] datas) {
    
            int length = datas.length;
    
            for (int index = 0; index < length; index++) {
    
                int minValueIndex = index;
    
                for (int compareIndex = index + 1; compareIndex < length; compareIndex++) {
    
                    if (datas[minValueIndex] > datas[compareIndex]) {
    
                        minValueIndex = compareIndex;
    
                    }
    
                }
    
                if (index != minValueIndex) {
    
                    int tempt = datas[minValueIndex];
                    datas[minValueIndex] = datas[index];
                    datas[index] = tempt;
    
                }
    
            }
    
    
        }

**三、直接插入排序**

public static void insertSort(int[] datas) {
    
            int length = datas.length;
            for (int index = 1; index < length; index++) {
    
                int temptIndex = index - 1;
                int value = datas[index];
    
                for (; temptIndex >= 0 && datas[temptIndex] > value; temptIndex--) {
                    datas[temptIndex + 1] = datas[temptIndex];
                }
                datas[temptIndex + 1] = value;
            }
        }

**四、希尔排序**

public static void shellSort(int[] datas) {
    
            int length = datas.length;
            int increment = length;
    
            while (increment > 0) {
                increment = increment / 2;
                for (int index = increment; index < length; index++) {
    
                    int temptIndex = index - increment;
                    int value = datas[index];
    
                    for (; temptIndex >= 0 && datas[temptIndex] > value; temptIndex -= increment) {
                        datas[temptIndex + increment] = datas[temptIndex];
                    }
                    datas[temptIndex + increment] = value;
    
                }
            }
    
        }

**五、归并排序**

public static int[] mergeSort(int[] datas) {
            int size = datas.length;
            if (size < 2) return datas;
            int[] left = Arrays.copyOfRange(datas, 0, size / 2);
            int[] right = Arrays.copyOfRange(datas, size / 2, size);
            return mergeArray(mergeSort(left),mergeSort(right));
        }
    
        public static int[] mergeArray(int[] left, int[] right) {
            int[] result = new int[left.length + right.length];
            for (int index = 0, i = 0, j = 0; index < result.length; index++) {
    
                if (i >= left.length) {
                    result[index] = right[j++];
                } else if (j >= right.length) {
                    result[index] = left[i++];
                } else if (left[i] > right[j]) {
                    result[index] = right[j++];
                } else {
                    result[index] = left[i++];
                }
            }
            return result;
        }

**六、快速排序**

public static void quickSort(int[] datas,int left,int right){
    
            if (left >= right){
                return;
            }
            int size = datas.length;
            int tempt = datas[left];
            int indexI = left;
            int indexJ = right - 1;
    
            while (indexI != indexJ){
                while (datas[indexJ] >= tempt && indexI < indexJ){
                    indexJ--;
                }
                while (datas[indexI] <= tempt && indexI < indexJ){
                    indexI ++;
                }
                if (indexI < indexJ){
    
                    int temptValue = datas[indexI];
                    datas[indexI] = datas[indexJ];
                    datas[indexJ] = temptValue;
    
                }
            }
    
            datas[left] = datas[indexI];
            datas[indexI] = tempt;
            quickSort(datas,left,indexI-1);
            quickSort(datas,indexI+1,right);
        }