[数据结构与算法]八大排序算法代码实现

冒泡排序:

  // j 与 j+1 两两比较
    public static void myBubbleSort(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

插入排序

public static void myInsertSort2(int[] arr) {
		for (int i=1; i<arr.length; i++){
			int insertI = arr[i];
			int j = i-1;
			while (j >= 0 && arr[j] > insertI){
				arr[j+1] = arr[j];
				j--;
			}
			arr[j+1] = insertI; // 这儿需要加一
		}
	}

快排

 public static void main(String[] args) {
        quickSort(new int[]{39, 28, 55, 87, 66, 3, 17, 39});
    }
    
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    // 一次切分: [小值子数组] ,切分元素, [大值子数组];    由大到小
    public static void quickSort(int[] arr, int left, int right) {
        int middle;
        if (left < right) {
            middle = partition(arr, left, right);
            quickSort(arr, left, middle - 1);
            quickSort(arr, middle + 1, right);
        }
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= pivot)
                right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot)
                left++;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }

归并排序

 // [有序子数组] 中间值 [有序子数组]  由细节到整体
    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right)
            return;
        int mid = left + (right - left) / 2;
        //向左递归进行分解
        mergeSort(arr, left, mid);
        //向右递归进行分解
        mergeSort(arr, mid + 1, right);
        //合并
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;

        int temp[] = new int[arr.length]; // 归并排序需要一个额外空间,此处临时数组只拷贝部分(left-right部分)
        for (int k = left; k <= right; k++) {
            temp[k] = arr[k];
        }

        for (int k = left; k <= right; k++) {
            if (i > mid) arr[k] = temp[j++];
            else if (j > right) arr[k] = temp[i++];
            else if (temp[i] > temp[j]) arr[k] = temp[j++];
            else arr[k] = temp[i++];
        }
    }

选择排序

// 找到真实的最小值
	public static void mySelectSort(int[] arr) {
		for (int i=0; i<arr.length; i++){
			int min = arr[i];
			int minIndex = i;

			for (int j=i+1; j<arr.length; j++){
				if(arr[j] < min){
					min = arr[j];
					minIndex = j;
				}
			}
			if(minIndex != i){
				int temp = arr[i];
				arr[i] = min;
				arr[minIndex] = temp;
			}
		}
	}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖