快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采 用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考 试如软考，考研中也常常出现快速排序的身影。总的说来，要直接默写出快速排序还是有一定难度的，因为本人就自己的理解对快速排序作了下白话解释，希望对大家理解有帮助，达到快速排序，快速搞定。 快速...
#ifndef BINTREE_H_INCLUDED #define BINTREE_H_INCLUDED#include <iostream> #include <queue> #include <stack> #include <string.h> using namespace std;template<class Type> class BinTree;template<class Type> class BinTreeNode { public:friend class BinTree<Type>;BinTreeNode():data(Type()),lChild(NULL),rChild(NULL){}BinTreeNode(Type d,BinTreeNode<Type> *m = NULL,BinTreeNode<Type> *n = NULL):data(d),lChil...
笔者在数据结构实验时进行该实现，二叉树是否为完全二叉树判定方法，主要便是观察两者的差别，完全二叉树本质：具有插入限制性，即在二叉树的实现基础上，需要满足除了最后一层之外，每层均满，既二叉树的倒数第三层及之上，每层均有左右结点，倒数第二层，对于一个节点的延申，只有有左节点的时候才能有右节点，对于不同节点，后一个结点可以拥有左节点的条件是前面所有结点的毒均为二。故将此条件简化代码化，来进行完全二叉树的...
堆：堆是具有特殊性质的二叉树每个结点都大于其左右儿子的的二叉树叫大顶堆每个结点都小于其左右儿子的二叉树叫做小顶堆堆排序图解： 给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。 首先根据该数组元素构建一个完全二叉树，得到 然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：20和16交换后导致16不满足堆的性质，因此需重新调整这样就得到了初始堆。即每次调整都是从父节点、左孩子节点、右孩...
二叉堆的概念二叉堆，BinaryHeap，是二叉树中的常见的一种结构。通常以最大堆和最小堆的形式呈现。最大堆指的是父节点大于等于孩子节点的value值，也就是说对于最大堆而言，根元素是二叉堆最大的元素。最小堆的概念是与最大堆的概念是相似的。下图是最大堆的示意图：二叉堆和排序之间的联系二叉堆最显著的特征就是根元素是二叉树元素间最大的或者最小的。因此每次将二叉树最大或者最小的元素取出来，同时保证每次进行这样的操作后，...
时间复杂度常数阶 O(1):跟问题规模没有关系int i = 0;int n = 100; printf("test"); printf("test"); printf("test"); printf("test"); //算法时间复杂度为O(1) 2、线性阶 O(n)：随着问题规模n的增大，对应的计算次数成直线增长int i = 0;int n = 100; int sum = 0; for(i=0; i<n; i++) {sum = sum + i; } //算法时间复杂度为O(n) 3、平方阶 O(n^2)：随着问题规模n的增大，对应的计算次数成抛物线增长in...
树这里 我分为二叉树和多路树java中常用的二叉树普通二叉树平衡二叉树(AVL)红黑树(相对放松一点的平衡二叉树，因为level可以超过1，而AVL的左右子树深度 相差不能超过1) 多路树，B树B-树B+树 原文：https://www.cnblogs.com/lanqingzhou/p/14346100.html
1package iYou.neugle.list;2 3publicclass MySeqStack<T> {4private Stack stack = new Stack();5 6class Stack {7publicint maxSize = 10;8public T[] data = (T[]) new Object[maxSize];9publicint top = -1;// 栈顶指针10 } 1112// 初始化栈13publicvoid SeqStackInit() { 14this.stack.top = -1; 15 System.out.println("栈初始化成功!"); 16 } 1718// 入栈19publicvoid SeqStackPush(T data) { 20if (this.sta...
今天的突然看集合底层的时候发现了好多算法和数据结构。再次就比较一下和汇总一下。数据结构分类：线性结构和非线性结构问题一：什么是线性和非线性；我个人的理解是：数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构；线性结构包括：数组，链表，队列，栈；非线性结构包括：树，图，表；详解：一.线性结构1.数组特点：我们都知道数组中的元素在内存中连续存储的，可以根据是下标快速访问元素，因此，查...
栈是一种先入后出的数据结构，最先进入的元素，却是最后出来，开发中，是否需要用到栈，只要记住它的这条特性就好了，这里我使用之前实现的DataStruct_Array类作为栈的底层容器实现，我们都知道对于栈来说，它需要提供给用户以下接口：1.getSize()：获取栈的实际数目2.isEmpty()：判断是否为空栈3.getCapacity()：获取栈的容量4.push()：入栈操作5.pop()：出栈操作（出栈顶元素）6.peek()：查看栈顶是哪位大神在实现Stack类之前，需...
驱动程序：public class Main { public static void main(String[] args) { int[] array={2,0,3,4,1,9,6,8,7,5}; print(Sort.bubbleSort(array, true));//冒泡 print(Sort.InsertionSort(array, true));//插入 print(Sort.mergeSort(array,true, "recursion"/*circulate*/));//归并 print(Sort.quickSort(array, true));//快速 print(Sort.radixSort(array, true));//基数 pr...
上篇总结中主要实践了算法的内排序的交换排序，那么接下来我们继续实践选择排序的两种：直接选择和堆排序算法。-----直接选择排序package com.sort;/*** 直接选择排序算法* @author weixing-yang** 算法思路：* 首先找出最大元素，将其与a[n-1]位置置换。* 然后在余下的n-1个元素中寻找最大元素，将其与a[n-2]位置置换。* 如此进行下去，知道n个元素排序完成。*/ public class SelectSort {public void selectSort(int[] arr, i...
使用标准库一、避免重复造轮子官方提供了很多库给我们用，是封装好的轮子，比如包fmt，我们多次使用它来打印数据。我们可以查看到其里面的实现：package fmtfunc Println(a ...interface{}) (n int, err error) {return Fprintln(os.Stdout, a...) }func Printf(format string, a ...interface{}) (n int, err error) {return Fprintf(os.Stdout, format, a...) }func Fprintf(w io.Writer, format string, a ...interface{}) (n i...
红黑树规则： 1、根节点与叶节点都是黑色节点 2、每个红色节点的两个子节点都是黑色节点，反之，不做要求，换句话说就是不能有连续两个红色节点 3、从根节点到所有叶子节点上的黑色节点数量是相同的一般对红黑树的讲述都是先给出这样的定义，这样想对不太容易理解的，而在算法4一书中，直接跳过这些规则，而讲述了红黑树与2-3树的等价性如果我们先了解2-3树，理解了红黑树与2-3树之间的关系，回过头就会发现红黑树不难2-3...
对于大量的数据，链表的线性访问时间太慢，不宜使用。我们介绍一种简单的数据结构，其大部分操作的平均时间为O(log N)。 (1)学习目标: 我们将要涉及到的数据结构叫做二叉查找树(binary search tree)。 我们将要了解如下内容:1.了解树是如何用于实现几个流行的操作系统中的文件系统的; 2.看到树如何能够用来计算算术表达式的值; 3.如何指出利用树支持以O(log N)平均时间进行的各种搜索操作，以及如何细化得到最坏情况时...