10種類のソートアルゴリズムのjava要約

数学科のcoding菜鳥として、もっとcodingを練習しなければなりません.1時間以上かけて手を振って並べ替えましたが、今回はコードを全部消してしまいました.やはり慣れていません.
ソートアルゴリズムは基礎の中の基礎であり、もっと練習しなければならない.ちょっと要点を話しましょう.
バブルソート:隣接する要素を1つずつ比較し、大きな要素を後ろに移動します.各エレメントは、ソートされていない配列の最後に最大のエレメントを配置できます.安定したソートを実現できます.時間複雑度はN-1+N-2+N-3+...+1 = N(N-1)/2 = O(N^2).空間複雑度O(1)
≪ソートの選択｜Select Sort｜Planning≫:ソートされていない要素ごとに最大を選択し、ソートされていない配列の末尾と交換します.不安定なソート.時間的複雑度はO(N^2),空間的複雑度はO(1)である.
≪ソートの挿入|Insert Sort|Planning≫:元の挿入ソートは、ソートされた配列に新しい要素を挿入し、ソートされた配列の最初の現在の要素より大きい位置を見つけて、順番に交換します.安定したソートとして実現でき,時間的複雑度はO(N^2)であり,配列が秩序化されている場合はO(N)であり,ソートされる配列のデータ状況に関係する.
二分挿入ソート:原理は挿入ソートと同じですが、ソートされた配列の最初の現在の要素より大きい位置を検索するときに二分検索が使用され、順序検索よりも効率的です.同様に安定したソートです.
ヒルソート:同様にソートを挿入します.ソートを挿入する時間的複雑さは、ソートされる配列のデータ状況に関係するため、この時間的複雑さは主に交換要素にある.ヒルソートの核心思想は、ソートされる配列全体を徐々に秩序化させることであり、ソートされる交換要素を挿入するたびに時間がかかります.1つのgapを設定することで、隣接するgapの要素ごとに直接挿入ソートを行います.分からない場合は、gapが1の場合は直接ソートを挿入します.gapが2なら1,3,5,7,9...位置の要素を直接挿入して並べ替えます.注意ヒルソートは不安定であり,その時間複雑度はO(n^1.3)~O(n^2)である.
集計ソート:分治の考え方を利用した.肝心なのはどのようにMergeするかで、具体的には言わないで、ネット上には多くの図解があって、書くのがすべてとても良いです.時間的複雑度O(Nlogn),空間的複雑度O(N)は,安定な秩序化を達成できる.
クイックソート:同様に分治の考え方を利用しており,ポイントはPartition関数にある.時間的複雑度はO(Nlogn)であり,最悪の場合O(N^2)は基本的に順序付けされた場合に劣り,各パーティションが均一であればあるほど速度が速くなる.したがって、通常はランダムスナップを採用し、分割点をランダムに選択します.不安定なソートです.
ヒープソート:不安定、時間複雑度O(Nlogn)
バケツソート数ソート:
バケツソート基準ソート:
プロジェクトの総合ソート:
対数:
また今度穴埋めしますね～

import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
		int[] arr = { 1, 11, 5, 10, 9, 4, 6, 4, 2, 0 };
		// BubbleSort(arr);
		// InsertionSort(arr);
		// BinaryInsertionSort(arr);
		// ShellSort(arr);
		// SelectionSort(arr);
		// MergeSort(arr);
		// QuickSort(arr);
		// HeapSort(arr);
		// BucketSort(arr);
		RadixSort(arr);
		for (int i : arr) {
			System.out.print(i + " ");
		}
		System.out.println();

		int testTime = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			// BubbleSort(arr1);
			// InsertionSort(arr1);
			// BinaryInsertionSort(arr1);
			// ShellSort(arr1);
			// SelectionSort(arr1);
			// MergeSort(arr1);
			// QuickSort(arr1);
			// HeapSort(arr1);
			// BucketSort(arr1);
			RadixSort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");
	}

	public static void BubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length - 1 - i; j++) {
				if (arr[j + 1] < arr[j]) {
					swap(arr, j, j + 1);
				}
			}
		}
	}

	public static void InsertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = i - 1; j >= 0; j--) {
				if (arr[j + 1] < arr[j])
					swap(arr, j, j + 1);
			}
		}
	}

	public static void BinaryInsertionSort(int[] arr) {
		if (arr == null || arr.length < 2)
			return;
		for (int i = 1; i < arr.length; i++) {
			int index = BinarySearch(arr, 0, i - 1, arr[i]);
			for (int j = i - 1; j >= index; j--)
				swap(arr, j, j + 1);
		}
	}

	public static int BinarySearch(int[] arr, int l, int r, int target) {
		int mid = 0;
		while (l <= r) {
			mid = l + ((r - l) >> 1);
			if (arr[mid] <= target)
				l = mid + 1;
			else
				r = mid - 1;
		}
		return l;
	}

	public static void ShellSort(int[] arr) {
		if (arr == null || arr.length < 2)
			return;
		int gap = arr.length;
		while (gap > 1) {
			gap = gap / 3 + 1;
			for (int i = gap; i < arr.length; i += gap) {
				for (int j = i - gap; j >= 0; j--) {
					if (arr[j + gap] < arr[j])
						swap(arr, j, j + gap);
				}
			}
		}
	}

	public static void SelectionSort(int[] arr) {
		if (arr == null || arr.length < 2)
			return;
		for (int i = 0; i < arr.length - 1; i++) {
			int index = 0;
			for (int j = 1; j < arr.length - i; j++) {
				if (arr[j] > arr[index])
					index = j;
			}
			swap(arr, index, arr.length - 1 - i);
		}
	}

	public static void MergeSort(int[] arr) {
		if (arr == null || arr.length < 2)
			return;
		MergeSort(arr, 0, arr.length - 1);
	}

	public static void MergeSort(int[] arr, int l, int r) {
		if (l < r) {
			int mid = l + ((r - l) >> 1);
			MergeSort(arr, l, mid);
			MergeSort(arr, mid + 1, r);
			Merge(arr, l, mid, r);
		}
	}

	public static void Merge(int[] arr, int l, int mid, int r) {
		int p1 = l;
		int p2 = mid + 1;
		int[] help = new int[r - l + 1];
		int i = 0;
		while (p1 <= mid && p2 <= r) {
			if (arr[p1] <= arr[p2])
				help[i++] = arr[p1++];
			else
				help[i++] = arr[p2++];
		}
		while (p1 <= mid)
			help[i++] = arr[p1++];
		while (p2 <= r)
			help[i++] = arr[p2++];
		for (int j = 0; j < help.length; j++)
			arr[l + j] = help[j];
	}

	public static void QuickSort(int[] arr) {
		if (arr == null || arr.length < 2)
			return;
		QuickSort(arr, 0, arr.length - 1);
	}

	public static void QuickSort(int[] arr, int l, int r) {
		if (l < r) {
			int[] p = Partition(arr, l, r);
			QuickSort(arr, l, p[0]);
			QuickSort(arr, p[1], r);
		}
	}

	public static int[] Partition(int[] arr, int l, int r) {
		swap(arr, r, l + (int) (Math.random() * (r - l + 1)));
		int val = arr[r]; // split standard.
		int p1 = l - 1;
		int p2 = r;
		while (l < p2) {
			if (arr[l] < val)
				swap(arr, l++, ++p1);
			else if (arr[l] > val)
				swap(arr, l, --p2);
			else
				l++;
		}
		swap(arr, p2++, r);
		return new int[] { p1, p2 };
	}

	public static void HeapSort(int[] arr) {
		if (arr == null || arr.length < 2)
			return;
		for (int i = 1; i < arr.length; i++)
			HeapInsert(arr, i);
		int size = arr.length;
		while (size > 1) {
			swap(arr, 0, --size);
			Heapify(arr, 0, size);
		}
	}

	public static void HeapInsert(int[] arr, int index) {
		while (index > 0) {
			if (arr[index] > arr[(index - 1) >> 1]) {
				swap(arr, index, (index - 1) >> 1);
				index = (index - 1) >> 1;
			} else
				return;
		}
	}

	public static void Heapify(int[] arr, int index, int size) {
		while ((index << 1) + 1 < size) {
			int leftchild = (index << 1) + 1;
			int childlargest = leftchild + 1 < size && arr[leftchild + 1] > arr[leftchild] ? leftchild + 1 : leftchild;
			int largest = arr[index] >= arr[childlargest] ? index : childlargest;
			if (largest == index)
				return;
			swap(arr, index, largest);
			index = largest;
		}
	}

	public static void BucketSort(int[] arr) {
		if (arr == null || arr.length < 2)
			return;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			min = arr[i] < min ? arr[i] : min;
			max = arr[i] > max ? arr[i] : max;
		}
		//     
		int[] buckets = new int[max - min + 1];
		for (int i = 0; i < arr.length; i++)
			arr[i] -= min;
		for (int i = 0; i < buckets.length; i++)
			buckets[i] = 0;
		for (int i = 0; i < arr.length; i++)
			buckets[arr[i]]++;
		int j = 0;
		for (int i = 0; i < buckets.length; i++)
			while (buckets[i] != 0) {
				arr[j++] = i;
				buckets[i]--;
			}
		for (int i = 0; i < arr.length; i++)
			arr[i] += min;
	}

	public static void RadixSort(int[] arr) {
		if (arr == null || arr.length < 2)
			return;
		final int radix = 10;
		RadixSort(arr, radix);
	}

	public static void RadixSort(int[] arr, int radix) {
		int maxbit = getmaxbit(arr, radix);
		int[] count = new int[radix];
		int[] buckets = new int[arr.length];

		for (int bit = 1; bit <= maxbit; bit++) {
			for (int i = 0; i < count.length; i++)
				count[i] = 0;
			for (int i = 0; i < arr.length; i++) {
				int digit = getdigit(arr[i], bit, radix);
				count[digit]++;
			}
			for (int i = 1; i < count.length; i++)
				count[i] += count[i - 1];
			for (int i = arr.length - 1; i >= 0; i--) {
				int digit = getdigit(arr[i], bit, radix);
				buckets[--count[digit]] = arr[i];
			}
			for (int i = 0; i < buckets.length; i++)
				arr[i] = buckets[i];
		}
	}

	public static int getmaxbit(int[] arr, int radix) {
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++)
			max = arr[i] > max ? arr[i] : max;
		int bit = 0;
		while (max != 0) {
			bit++;
			max /= radix;
		}
		return bit;
	}

	public static int getdigit(int val, int bit, int radix) {
		return (int) ((val / (int) Math.pow(radix, bit - 1)) % radix);
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	// for test
	public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			// arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue *
			// Math.random());
			arr[i] = (int) ((maxValue + 1) * Math.random());
		}
		return arr;
	}

	// for test
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	// for test
	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}