HeapSort.java
· 1.3 KiB · Java
原始檔案
import java.util.*;
public class HeapSort {
public void sort(int arr[])
{
int N = arr.length;
for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
for (int i = N - 1; i > 0; i--) {
int x = arr[0];
arr[0] = arr[i];
arr[i] = x;
heapify(arr, i, 0);
}
}
void heapify(int arr[], int N, int i)
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < N && arr[l] > arr[largest])
largest = l;
if (r < N && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, N, largest);
}
}
static void printArray(int arr[])
{
int N = arr.length;
for (int i = 0; i < N; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int i, n, arr[];
Scanner s = new Scanner(System.in);
System.out.println("Enter no. of elements in aray:");
n = s.nextInt();
arr = new int[n];
System.out.println("Enter " + n + " integers:");
for (i = 0;i<n; i++)
arr[i] = s.nextInt();
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
| 1 | import java.util.*; |
| 2 | public class HeapSort { |
| 3 | public void sort(int arr[]) |
| 4 | { |
| 5 | int N = arr.length; |
| 6 | |
| 7 | for (int i = N / 2 - 1; i >= 0; i--) |
| 8 | heapify(arr, N, i); |
| 9 | |
| 10 | for (int i = N - 1; i > 0; i--) { |
| 11 | |
| 12 | int x = arr[0]; |
| 13 | arr[0] = arr[i]; |
| 14 | arr[i] = x; |
| 15 | |
| 16 | heapify(arr, i, 0); |
| 17 | } |
| 18 | } |
| 19 | |
| 20 | void heapify(int arr[], int N, int i) |
| 21 | { |
| 22 | int largest = i; |
| 23 | int l = 2 * i + 1; |
| 24 | int r = 2 * i + 2; |
| 25 | |
| 26 | if (l < N && arr[l] > arr[largest]) |
| 27 | largest = l; |
| 28 | |
| 29 | if (r < N && arr[r] > arr[largest]) |
| 30 | largest = r; |
| 31 | |
| 32 | if (largest != i) { |
| 33 | int swap = arr[i]; |
| 34 | arr[i] = arr[largest]; |
| 35 | arr[largest] = swap; |
| 36 | |
| 37 | heapify(arr, N, largest); |
| 38 | } |
| 39 | } |
| 40 | static void printArray(int arr[]) |
| 41 | { |
| 42 | int N = arr.length; |
| 43 | |
| 44 | for (int i = 0; i < N; ++i) |
| 45 | System.out.print(arr[i] + " "); |
| 46 | System.out.println(); |
| 47 | } |
| 48 | |
| 49 | public static void main(String args[]) |
| 50 | { |
| 51 | int i, n, arr[]; |
| 52 | |
| 53 | Scanner s = new Scanner(System.in); |
| 54 | System.out.println("Enter no. of elements in aray:"); |
| 55 | n = s.nextInt(); |
| 56 | |
| 57 | arr = new int[n]; |
| 58 | |
| 59 | System.out.println("Enter " + n + " integers:"); |
| 60 | |
| 61 | for (i = 0;i<n; i++) |
| 62 | arr[i] = s.nextInt(); |
| 63 | |
| 64 | HeapSort ob = new HeapSort(); |
| 65 | ob.sort(arr); |
| 66 | |
| 67 | System.out.println("Sorted array is"); |
| 68 | printArray(arr); |
| 69 | } |
| 70 | |
| 71 | |
| 72 | } |
| 73 |