首页 > 试题广场 >

排序（堆排序）

[编程题]排序（堆排序）

热度指数：4243 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个n代表有n个数字，然后你需要使用堆排序将这些数字从小到大排好。

输入描述:

第一行输入一个n，代表有n个数字
第二行输入n个数

输出描述:

输出排序好后的n个数

示例1

输入

4
4 3 2 1

输出

1 2 3 4

算法知识视频讲解

Spectre_

#include<cstdio>

void swap(int *arr, int i, int j) {
    if (i == j) return;
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

void heapify(int *arr, int index, int *heapSize) {
    int left = 2 * index + 1;
    while (left < *heapSize) {
        int largest = 2 * index + 2 < *heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) break;
        swap(arr, largest, index);
        index = largest;
        left = 2 * index + 1;
    }
}

void heapSort(int *arr, int *heapSize) {
    while (*heapSize > 0) {
        swap(arr, 0, *heapSize - 1);
        --(*heapSize);
        heapify(arr, 0, heapSize);
    }
}

void heapInsert(int *arr, int *heapSize) {
    scanf("%d", &arr[*heapSize]);
    int cur = *heapSize, parent = (*heapSize - 1) / 2;
    while (arr[cur] > arr[parent]) {
        swap(arr, cur, parent);
        cur = parent;
        parent = (cur - 1) / 2;
    }
    ++(*heapSize);
}

int main() {
    int n, heapSize = 0;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; ++i) heapInsert(arr, &heapSize);
    heapSort(arr, &heapSize);
    for (int i = 0; i < n; ++i) printf("%d ", arr[i]);
    return 0;
}

发表于 2021-09-11 15:19:41 回复(0)

曹格杨

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for(int i=0;i<n;i++){
            array[i] = sc.nextInt();
        }
        heapSort(array);
        for(int a:array){
            System.out.print(a+" ");
        }
    }
    public static void heapSort(int[] array){
        creatMaxHeap(array);
        int end = array.length-1;
        while(end>0){
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            adjustDown(array,0,end);
            end--;
        }
    }
    public static void creatMaxHeap(int[] array){
        for(int i=(array.length/2)-1;i>=0;i--){
            adjustDown(array,i,array.length);
        }
    }
    public static void adjustDown(int[] array,int root,int len){
        int parent = root;
        int child = 2*parent+1;
        while(child<len){
            if(child+1<len && array[child]<array[child+1]){
                child++;
            }
            if(array[parent]<array[child]){
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }
}

发表于 2021-03-31 14:46:17 回复(0)

一只双非鼠

import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int MAXN = 1001;
    static int[] nums = new int[MAXN];
    static int n;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while(in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            for(int i = 0; i < n ; i ++) {
                in.nextToken();
                nums[i] = (int) in.nval;
            }
            // heapSort1();
            heapSort2();
            out.print(nums[0]);
            for(int i = 1; i < n; i ++) 
                out.print(" " + nums[i]);
            out.println();
        }
        out.flush();
        out.close();
        br.close();
    }
    public static void heapSort1() {
        // 从顶到底建立大根堆
        for(int i = 0; i < n; i ++) {
            heapInsert(i);
        } 
        int size = n;
        while(size > 1) {
            swap(0, -- size);
            heapify(0, size);
        }
    }
    public static void heapSort2() {
        for(int i = n - 1; i >= 0; i --) {
            heapify(i, n);
        }
        int size = n;
        while(size > 1) {
            swap(0, -- size);
            heapify(0, size);
        }
    }
    public static void heapInsert(int i) {
        // 孩子比父节点大，上浮，交换
        while(nums[i] > nums[(i - 1) / 2]) {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2; 
        }
    }
    public static void heapify(int root, int size) {
        int child = 2 * root + 1;
        while(child < size) {
            if(child + 1 < size && nums[child] < nums[child + 1]) child ++;
            if(nums[root] > nums[child]) break; // 无需交换
            swap(root, child);
            root = child;
            child = 2 * root + 1;
        }
    }
    public static void swap(int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

编辑于 2024-02-19 00:14:30 回复(0)

I_wanna

import sys

for line in sys.stdin:
    line = line.strip()
    if len(line)<=0:break
    n = int(line)

    nums = input().strip().split(' ')
    nums = [int(x) for x in nums]

    def heapify(arr,n,i):
        largest = i
        lson = i*2+1
        rson = i*2+2
        if lson<n and arr[largest]<arr[lson]:
            largest = lson
        if rson<n and arr[largest]<arr[rson]:
            largest = rson
        if largest!=i:
            arr[largest],arr[i] = arr[i],arr[largest]
            heapify(arr,n,largest)
            
    def heap_sort(arr,n):
        for i in range(int(n/2)-1,-1,-1):
            heapify(arr,n,i)
        for i in range(n-1,0,-1):
            arr[i],arr[0] = arr[0],arr[i]
            heapify(arr,i,0)
        return arr
    
    nums = heap_sort(nums,len(nums))
    ans = ''
    for i in range(len(nums)):
        ans+=(str(nums[i]))
        if i!=len(nums)-1:ans+=' '
    print(ans)

面试常见手撕堆排序，主要分为两个函数：①调整堆函数 heapify 和 ②排序函数heap_sort，其中heapify是用递归的思路，逐渐往子结点调整直到不能再调整，heap_sort的思路则是：先调用heapify调整成堆，然后从后往前遍历，并且每一次交换尾部结点和头部结点，只调整无序的部分，有序的部分逐渐增加直到覆盖整个数组。

发表于 2023-08-07 12:40:46 回复(0)

thanks__start

package heapSort;  import java.util.Arrays; import java.util.Scanner;  public class heapSort { public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);  int n = scanner.nextInt();  int[] arr = new int[n];  for(int i = 0 ; i < n ; i++){
            arr[i] = scanner.nextInt();  } HeapSort(arr);  System.out.println(Arrays.toString(arr));  } public static void HeapSort(int[] arr){ /*  将待排序序列构造成一个大顶堆  此时，整个序列的最大值就是堆顶的根节点。*/  /*adjustHeap( arr,1,arr.length);  adjustHeap( arr,0,arr.length);*/  for(int i = arr.length / 2 - 1 ; i >= 0 ; i--){ adjustHeap(arr,i,arr.length);  } int tmp = 0;  for(int i = arr.length - 1 ; i > 0 ; i--){
            tmp = arr[i];  arr[i] = arr[0];  arr[0] = tmp;  adjustHeap(arr,0,i);  }
    } public static void adjustHeap(int[] arr, int start , int end){ int tmp = arr[start];  for(int i = start * 2 + 1 ; i < end ; i = i * 2 + 1){ if(i + 1 < end && arr[i] < arr[i + 1]){
                i++;  } if(arr[i] > tmp){
                arr[start] = arr[i];  start = i;  }else{ break;  }
        }
        arr[start] = tmp;  }
}

发表于 2023-07-08 10:30:13 回复(0)

C/C++

牛客382637577号

#include<iostream>
using namespace std;

const int N = 100010;
int n, h[N], size1;

void down(int u) {
	int t = u;
	if (u * 2 <= size1 && h[u * 2] < h[t]) t = u * 2;
	if (u * 2 + 1 <= size1 && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
	if (u != t) {
		swap(h[u], h[t]);
		down(t);
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
	size1 = n;

	for (int i = n / 2; i; i--) down(i);
    while( n --){
	printf("%d ", h[1]);
	h[1] = h[size1];
	size1--;
	down(1);
    }
	return 0;
}

发表于 2022-08-19 16:18:10 回复(0)

牛客422042720号

#include<iostream>
#include<vector>
using namespace std;

void heap_adjust(vector<int>&nums,int cur,int n)//调整大顶堆
{
    int tmp=nums[cur];
    while(cur<n)
    {
        int l=2*cur+1;
        int r=2*cur+2;
        if(l<n&&nums[cur]<nums[l])
            nums[cur]=nums[l];
        if(r<n&&nums[cur]<nums[r])
            nums[cur]=nums[r];
        if(nums[cur]==tmp)
            break;
        if(nums[cur]==nums[l])
            cur=l;
        else
            cur=r;
        nums[cur]=tmp; 
    }
}

void heap_sort(vector<int>&nums,int n)
{
    for(int i=n/2-1;i>=0;--i)//构建大顶堆
    {
        heap_adjust(nums,i,n);
    }
    
    for(int i=n-1;i>0;--i)
    {
        int temp=nums[0];
        nums[0]=nums[i];
        nums[i]=temp;
        heap_adjust(nums,0,i);
    }
    
    
}

int main()
{
    int count;
    cin>>count;
    vector<int>nums(count);
    for(int i=0;i<count;++i)
    {
        cin>>nums[i];
    }
    heap_sort(nums,count);
    for(int i=0;i<count;++i)
    {
        cout<<nums[i]<<" ";
    }
}

编辑于 2022-08-18 15:43:21 回复(0)

FARO_Z

import java.util.Scanner;

public class Main {
    private static final Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        heapSort(arr);
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    public static void heapSort(int[]arr) {
        if (arr==null || arr.length<2) return;
        buildMaxHeap(arr);
        for (int i = arr.length-1; i>0 ; i--) {
            int tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
            maxHeapAdjust(arr,0,i);
        }
    }

    private static void buildMaxHeap(int[]arr) {
        if (arr==null || arr.length<2) return;
        int bottomRowLastNodeIndex = (arr.length - 1) / 2;
        for (int i = bottomRowLastNodeIndex; i >=0 ; i--) {
            maxHeapAdjust(arr,i,arr.length);
        }
    }

    private static void maxHeapAdjust(int[]arr,int index,int heapSize) {
        if (index>=heapSize) return;
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int maxValIndex = index;
        if (left<heapSize && arr[left]>arr[maxValIndex]) {
            maxValIndex = left;
        }
        if (right<heapSize && arr[right]>arr[maxValIndex]) {
            maxValIndex = right;
        }
        if (maxValIndex==index) {
            return;
        }
        int tmp = arr[index];
        arr[index] = arr[maxValIndex];
        arr[maxValIndex] = tmp;
        maxHeapAdjust(arr,maxValIndex,heapSize);
    }
}

发表于 2022-07-16 02:36:41 回复(0)

Java

牛客437925965号

import java.util.*;
public class Main {
    public static void main(String[] arg){
        Scanner in =new Scanner(System.in);
        int n=in.nextInt();
        int[] nums=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=in.nextInt();
        }
        
        heapSort(nums);
        
    }
    public static void heapSort(int[] nums){
        int n=nums.length;
        for(int i=n/2-1;i>=0;i--){
            //从最后一个非叶子节点开始调整
            heapAdjust(nums,i,n);
        }
        for(int i=n-1;i>0;i--){
            swap(nums,0,i);
            heapAdjust(nums,0,i);
        }
        
        for(int i=0;i<n;i++){
            System.out.print(nums[i]+" ");
        }
        
    }
    //将根节点沉入已构建的大顶堆
    public static void heapAdjust(int[] nums,int i,int n){
        for(int k=2*i+1;k<n;k=2*k+1){//找左节点
            if(k+1<n&&nums[k+1]>nums[k]){
                //右节点更大则换为右节点  更大的往上浮
                k++;
            }
            if(nums[k]>nums[i]){
                swap(nums,i,k);
                i=k;
            }else
                break;
        }  
    }
    public static void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
        return;
    }
}

发表于 2021-03-27 16:02:44 回复(0)