🌐 AI搜索 & 代理 主页
Skip to content

Commit 2bddacb

Browse files
author
Lord-of-Algorithms
committed
Add Sorting Algorithms: Bubble, Selection, Insertion, Merge, Heap, and Quick
1 parent 38153ef commit 2bddacb

File tree

10 files changed

+662
-0
lines changed

10 files changed

+662
-0
lines changed

‎src/sorting/BubbleSort.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package sorting;
2+
3+
public class BubbleSort {
4+
5+
/**
6+
* Sorts the provided array using the Bubble Sort algorithm.
7+
*
8+
* @param array The array to be sorted.
9+
*/
10+
public static void bubbleSort(int[] array) {
11+
for (int i = 0; i < array.length - 1; i++) {
12+
boolean swapped = false;
13+
for (int j = 0; j < array.length - 1 - i; j++) {
14+
// Compare adjacent elements
15+
if (array[j] > array[j + 1]) {
16+
// Swap if they are in the wrong order
17+
int temp = array[j];
18+
array[j] = array[j + 1];
19+
array[j + 1] = temp;
20+
swapped = true;
21+
}
22+
}
23+
// If no two elements were swapped, the array is sorted
24+
if (!swapped) {
25+
break;
26+
}
27+
}
28+
}
29+
30+
public static void main(String[] args) {
31+
int[] array = {64, 34, 25, 12, 22, 11, 90};
32+
33+
System.out.println("Original Array:");
34+
for (int value : array) {
35+
System.out.print(value + " ");
36+
}
37+
38+
bubbleSort(array);
39+
40+
System.out.println("\n\nSorted Array:");
41+
for (int value : array) {
42+
System.out.print(value + " ");
43+
}
44+
}
45+
}

‎src/sorting/InsertionSort.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package sorting;
2+
3+
public class InsertionSort {
4+
5+
/**
6+
* Sorts the provided array using the Insertion Sort algorithm.
7+
*
8+
* @param array The array to be sorted.
9+
*/
10+
public static void insertionSort(int[] array) {
11+
int n = array.length;
12+
for (int i = 1; i < n; i++) {
13+
int temp = array[i];
14+
15+
// Move elements of array[0..i-1], that are greater than temp,
16+
// to one position ahead of their current position
17+
int j = i;
18+
while (j > 0 && array[j - 1] > temp) {
19+
array[j] = array[j - 1];
20+
--j;
21+
}
22+
array[j] = temp;
23+
}
24+
}
25+
26+
public static void main(String[] args) {
27+
int[] array = {64, 25, 12, 22, 11, 90, 18};
28+
29+
System.out.println("Original Array:");
30+
for (int value : array) {
31+
System.out.print(value + " ");
32+
}
33+
34+
insertionSort(array);
35+
36+
System.out.println("\n\nSorted Array:");
37+
for (int value : array) {
38+
System.out.print(value + " ");
39+
}
40+
}
41+
}

‎src/sorting/MergeSort.java‎

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
package sorting;
2+
3+
public class MergeSort {
4+
5+
/**
6+
* Sorts the provided array using the Merge Sort algorithm.
7+
*
8+
* @param array The array to be sorted.
9+
*/
10+
public static void mergeSort(int[] array) {
11+
if (array == null || array.length <= 1) {
12+
return; // Exit the method early if the array is null, empty, or contains only one element, as no sorting is needed.
13+
}
14+
int[] auxiliaryArray = new int[array.length]; // auxiliary array for merging
15+
mergeSortRec(array, auxiliaryArray, 0, array.length - 1);
16+
}
17+
18+
/**
19+
* Recursive method that divides the array into halves, sorts them and merges them.
20+
*
21+
* @param array The array to be sorted.
22+
* @param auxArray Auxiliary array used for merging sorted halves.
23+
* @param start The starting index of the segment of the array to be sorted.
24+
* @param end The ending index of the segment of the array to be sorted.
25+
*/
26+
private static void mergeSortRec(
27+
int[] array,
28+
int[] auxArray,
29+
int start,
30+
int end
31+
) {
32+
if (start < end) {
33+
int mid = (start + end) / 2;
34+
mergeSortRec(array, auxArray, start, mid); // Sort the first half
35+
mergeSortRec(array, auxArray, mid + 1, end); // Sort the second half
36+
mergeBothParts(array, auxArray, start, mid + 1, end); // Merge sorted halves
37+
}
38+
}
39+
40+
/**
41+
* Merges two sorted halves of the array.
42+
*
43+
* @param array The original array containing all elements.
44+
* @param auxArray Auxiliary array used to help merge elements.
45+
* @param left The starting index of the first sorted half.
46+
* @param right The starting index of the second sorted half.
47+
* @param end The ending index of the second sorted half.
48+
*/
49+
private static void mergeBothParts(
50+
int[] array,
51+
int[] auxArray,
52+
int left,
53+
int right,
54+
int end
55+
) {
56+
int start = left;
57+
int mid = right - 1;
58+
int itemsCount = end - left + 1;
59+
60+
int i = 0;
61+
62+
// Merge elements and store in auxArray
63+
while (left <= mid &&
64+
right <= end) {
65+
66+
if (array[left] <
67+
array[right]) {
68+
auxArray[i++] = array[left++];
69+
} else {
70+
auxArray[i++] = array[right++];
71+
}
72+
}
73+
74+
// Copy remaining elements from the first half
75+
while (left <= mid) {
76+
auxArray[i++] = array[left++];
77+
}
78+
79+
// Copy remaining elements from the second half
80+
while (right <= end) {
81+
auxArray[i++] = array[right++];
82+
}
83+
84+
// Copy back the merged elements to the original array
85+
for (i = 0; i < itemsCount; i++) {
86+
array[start + i] = auxArray[i];
87+
}
88+
}
89+
90+
/**
91+
* Main method to demonstrate the Merge Sort algorithm.
92+
*/
93+
public static void main(String[] args) {
94+
int[] array = {64, 25, 12, 22, 11, 90, 18};
95+
96+
System.out.println("Original Array:");
97+
for (int value : array) {
98+
System.out.print(value + " ");
99+
}
100+
101+
mergeSort(array);
102+
103+
System.out.println("\n\nSorted Array:");
104+
for (int value : array) {
105+
System.out.print(value + " ");
106+
}
107+
}
108+
}

‎src/sorting/SelectionSort.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package sorting;
2+
3+
public class SelectionSort {
4+
5+
/**
6+
* Sorts the provided array using the Selection Sort algorithm.
7+
*
8+
* @param array The array to be sorted.
9+
*/
10+
public static void selectionSort(int[] array) {
11+
int n = array.length;
12+
// One by one move the boundary of the unsorted part
13+
for (int i = 0; i < n - 1; i++) {
14+
// Assume the first element is the minimum
15+
int minIndex = i;
16+
// Check the rest of the array to find the true minimum
17+
for (int j = i + 1; j < n; j++) {
18+
if (array[j] < array[minIndex]) {
19+
minIndex = j; // Found a new minimum, remember its index
20+
}
21+
}
22+
// Swap the found minimum element with the first
23+
// element of the unsorted part
24+
int temp = array[minIndex];
25+
array[minIndex] = array[i];
26+
array[i] = temp;
27+
}
28+
}
29+
30+
public static void main(String[] args) {
31+
int[] array = {64, 25, 12, 22, 11, 90, 18};
32+
33+
System.out.println("Original Array:");
34+
for (int value : array) {
35+
System.out.print(value + " ");
36+
}
37+
38+
selectionSort(array);
39+
40+
System.out.println("\n\nSorted Array:");
41+
for (int value : array) {
42+
System.out.print(value + " ");
43+
}
44+
}
45+
}

‎src/sorting/heap/HeapSortIterative.java‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
package sorting.heap;
2+
3+
/**
4+
* Implements the Heap Sort algorithm using an iterative approach.
5+
*/
6+
public class HeapSortIterative {
7+
8+
/**
9+
* Sorts an array using the Heap Sort algorithm.
10+
*
11+
* @param array The array to be sorted.
12+
*/
13+
public static void sort(int[] array) {
14+
int n = array.length;
15+
// Build a heap from the array
16+
buildHeap(array, n);
17+
for (int i = n - 1; i > 0; i--) {
18+
// Swap the root of the heap with the last element of the unsorted part
19+
int root = array[0];
20+
array[0] = array[i];
21+
array[i] = root;
22+
// Heapify the root element to maintain the heap property
23+
heapify(array, 0, i);
24+
}
25+
}
26+
27+
/**
28+
* Transforms an array into a max heap.
29+
*
30+
* @param array The array to transform into a heap.
31+
* @param size The number of elements in the array.
32+
*/
33+
private static void buildHeap(int[] array, int size) {
34+
for (int i = size / 2 - 1; i >= 0; i--) {
35+
heapify(array, i, size);
36+
}
37+
}
38+
39+
/**
40+
* Ensures the heap property for a subtree rooted at the index i.
41+
*
42+
* @param array The heap array.
43+
* @param i The root index of the subtree.
44+
* @param size The size of the heap (or subheap during sorting).
45+
*/
46+
private static void heapify(int[] array, int i, int size) {
47+
int examined = array[i];
48+
while (i < size / 2) { // Only non-leaf nodes need to be heapified
49+
int largestChildIndex =
50+
getLargestChildIndex(array, i, size);
51+
if (examined >= array[largestChildIndex]) {
52+
break; // The heap property is satisfied
53+
} else {
54+
// Overwrite the current node with the value of its largest child
55+
array[i] = array[largestChildIndex];
56+
// Move the index to the largest child to continue the process down the tree
57+
i = largestChildIndex;
58+
}
59+
}
60+
// Place the original root value at the final position determined by the last iteration
61+
array[i] = examined;
62+
}
63+
64+
/**
65+
* Returns the index of the largest child of a given node.
66+
*
67+
* @param array The heap array.
68+
* @param index The index of the node.
69+
* @param size The size of the heap.
70+
* @return The index of the largest child.
71+
*/
72+
private static int getLargestChildIndex(
73+
int[] array,
74+
int index,
75+
int size
76+
) {
77+
int leftIndex = 2 * index + 1;
78+
int rightIndex = leftIndex + 1;
79+
if (rightIndex < size &&
80+
array[leftIndex] <
81+
array[rightIndex]) {
82+
return rightIndex; // Right child is larger
83+
} else {
84+
return leftIndex; // Left child is larger or only child
85+
}
86+
}
87+
}

‎src/sorting/heap/HeapSortMain.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package sorting.heap;
2+
3+
/**
4+
* Demonstrates the use of the Heap Sort algorithm in both iterative and recursive forms.
5+
* This class allows for switching between different implementations of Heap Sort
6+
* based on the provided sorting nature.
7+
*/
8+
public class HeapSortMain {
9+
10+
/**
11+
* Defines the nature of the sorting method to be used in the Heap Sort.
12+
* It supports both iterative and recursive approaches.
13+
*/
14+
private enum SortNature {
15+
ITERATIVE,
16+
RECURSIVE
17+
}
18+
19+
/**
20+
* Sorts an array using either the iterative or recursive Heap Sort method
21+
* as specified by the {@code sortNature} parameter.
22+
*
23+
* @param array The array to be sorted.
24+
* @param sortNature The type of sorting method to use, either ITERATIVE or RECURSIVE.
25+
* @throws IllegalArgumentException if an unsupported sorting nature is provided.
26+
*/
27+
private static void sort(int[] array, SortNature sortNature) {
28+
if (array == null || array.length <= 1) {
29+
return; // Exit the method early if the array is null, empty, or contains only one element, as no sorting is needed.
30+
}
31+
switch (sortNature) {
32+
case ITERATIVE:
33+
HeapSortIterative.sort(array);
34+
break;
35+
case RECURSIVE:
36+
HeapSortRecursive.sort(array);
37+
break;
38+
default:
39+
throw new IllegalArgumentException("Unsupported sorting nature: " + sortNature);
40+
}
41+
}
42+
43+
/**
44+
* Main method to demonstrate the Heap Sort algorithm.
45+
*/
46+
public static void main(String[] args) {
47+
int[] array = {64, 25, 12, 22, 11, 90, 18};
48+
49+
System.out.println("Original Array:");
50+
for (int value : array) {
51+
System.out.print(value + " ");
52+
}
53+
54+
sort(array, SortNature.RECURSIVE);
55+
56+
System.out.println("\n\nSorted Array:");
57+
for (int value : array) {
58+
System.out.print(value + " ");
59+
}
60+
}
61+
}

0 commit comments

Comments
 (0)