快排和堆排序

别看这个简单也基础,但是真的面试的时候会让你写,纸上手写,嗯

快排

private static void quickSort(int[] test, int start, int end) {
        //quick sort的主程序
        if(start < end){
            int q = partition(test, start, end);
            quickSort(test, start, q-1);
            quickSort(test, q+1, end);
        }

    }

    private static int partition(int[] test, int start, int end) {
        //完成一次划分
        //主元选择test[end]
        int pivot = test[end];
        int i = start - 1;
        for(int j = start; j < end; j++){
            if(test[j] <= pivot){
                i++;
                //交换test[i]和test[j]
                int t = test[i];
                test[i] = test[j];
                test[j] = t;
            }
        }
        //i+1的位置即是pivot的位置
        //交换test[i+1]和pivot
        int t1 = test[i+1];
        test[i+1] = test[end];
        test[end] = t1;
        return i+1;
    }

堆排序

public static void heapSort(int[] test){
         //建堆
         buildHeap(test);
         for(int heapSize = test.length - 1; heapSize >= 1; heapSize--){
             //交换test[heapSize]和test[0]的位置
             int t = test[0];
             test[0] = test[heapSize];
             test[heapSize] = t;
             //维护堆的性质
             maxHeapify(test, heapSize, 0);
         }
     }
    private static void maxHeapify(int[] test, int heapSize, int i) {
        //维护堆的性质
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        //找出三者最大的
        int largest;
        if(left < heapSize && test[left] > test[i]){
            largest = left;
        }else{
            largest = i;
        }
        if(right < heapSize && test[right] > test[largest]){
            largest = right;
        }
        if(i != largest){
            //交换test[i]和test[largest]
            int t = test[i];
            test[i] = test[largest];
            test[largest] = t;
            //递归
            maxHeapify(test, heapSize, largest);
        }

    }
    private static void buildHeap(int[] test) {
        //建堆
        for(int i = test.length / 2; i >= 0; i--){
            maxHeapify(test, test.length, i);
        }

    }

main函数:

int test = {2,3,1,1,5,6,7,7,8,4,9,11};
//quickSort(test, 0, test.length-1);
heapSort(test);
for(int x : test){
    System.out.print(x+" ");
}     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ1299: [LLH邀请赛]巧克力棒(Nim游戏)

Description TBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒,或是将一根取出的巧克力棒吃掉正整数长度。TBL先手两人轮流,无法操...

30510
来自专栏书山有路勤为径

射击气球

LeetCode 452. Minimum Number of Arrows to Burst Balloons 已知在一个平面上有一定数量的气球,平面可以看...

661
来自专栏我是业余自学C/C++的

链栈 原

链栈就是栈结构的链表形式。其他的操作和数组表示栈一摸一样。 下面是具体的代码实现:

621
来自专栏BY的专栏

Swift的HMAC和SHA1加密

3444
来自专栏一“技”之长

Objective-C中NSArray类的解读

    NSArray数组类是Objective-C语言中常用的也是重要的一个类,除了开发中常用到的一些基础功能,NSArray及其相关类中还封装了许多更加强大...

672
来自专栏有趣的Python

数据机构探险之图(下)篇:代码实战数据机构探险之图篇(代码编写)

数据机构探险之图篇(代码编写) 图的存储(邻接矩阵) & 图的深度优先 & 广度优先 图的编码实战-最小生成树(普里姆算法) 图的编码实战-最小生成树之克鲁斯卡...

3515
来自专栏nnngu

算法03 七大排序之:直接插入排序和希尔排序

上一篇总结了直接选择排序和堆排序,这一篇要总结的是插入排序中的直接插入排序和希尔排序,我们主要从以下几点进行总结。 1、直接插入排序及算法实现 2、希尔排序及算...

3316
来自专栏编程之旅

iOS开发——大大节省代码量的小技巧

784
来自专栏算法修养

CodeForces 639 A

Bear and Displayed Friends time limit per test2 seconds memory limit per tes...

2634
来自专栏iOS Developer

iOS开发之AES+Base64数据混合加密与解密

803

扫码关注云+社区