快排算法的实现与讲解(java/C++)

快排的算法其实不复杂,但是很少时候,偶尔整的自己头晕,所以写一篇博客,以免以后忘记。

假设我们的数组为:{5,2,1,8,9,3,7,0,4,6},一共10个数字,现在需要将这个数组进行排序。首先我们需要找一个基准数,其实就是参照物,得有个东西跟你对比吧?不然怎么可以呈现出你的美?

假设左边为i=0; 右边j = 9;

方法很简单,分别从数组的左右边两段进行“探测”。首先是左边移动,最左边的第一个数字是5,而最右边的数字是6。

6 >= 5 条件成立,接着左边往右边移动一位(j–)

……

4>=5条件不成立,这个时候就换一下位置,4跟5换。现在的数组应该就是这样子:{4,2,1,8,9,3,7,0,5,6}

接着轮到右边探测,左边的数字已经被替换为4,而右边的是5(因为j自减了一次);那么现在条件对比:

5>=4条件成立,右边往左边靠拢(i++)

5>=2条件成立,右边往左边靠拢(i++)

……

5>=8条件不成立,换位置:{4,2,1,5,9,3,7,0,8,6}

到此,第一轮交换结束。接下来j继续向左挪动(再友情提醒,每次必须是j先出发)。他发现了0(比基准数5要小,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下:

{4,2,1,0,9,3,7,5,8,6}

第二次交换结束,“探测”继续。接着轮到i继续向右挪动,他发现了9(比基准数5要大,满足要求)之后又停了下来。交换之后的序列如下:

{4,2,1,0,5,3,7,9,8,6}

….以此类推,哨兵i继续向右移动,悲剧!!!此时i和j撞上了,说明此时“探测”结束。我们将基准数5和3进行交换。交换之后的序列如下:

{4,2,1,0,3,5,7,9,8,6}

到此“探测”真正结束。此时以基准数5为分界点,5左边的数都小于等于5,5右边的数都大于等于5。

回顾一下刚才的过程,其实j的使命就是要找小于基准数(5)的数,而哨兵i的使命就是要找大于基准数(5)的数,直到i和j撞在一起为止为止。

那么现在数据可以区分为两组:

{4,2,1,0,3,        5       ,7,9,8,6}

左边:4  2  1  0  3

右边:7  9  8  6

数组被分为了两组,然后按照直接的方法进行对比,只是开始i=0;j=9,要变为(先从左边开始):

指针位置:i=0; j=4

数组:4  2  1  0  3

还是上一张图吧,比较好理解:

wKiom1MUSRPjUTOIAAC-kWvhNhc591

注:图片是网上找的,数组的排序跟我的不一致,但是看的明白。

最后:

  • 快排的原理很简单;
  • 就是把数组分为两节;
  • 左边的是最小的,而右边的是最大的;
  • 然后再拿左、右边的来继续递归,递归的原理也一样,也是拆分为两节,以此类推。

上代码吧,我写了java跟c的代码:

2.java代码:

public static void main(String[] args) {
    int[] arr = {5,2,1,8,9,3,7,0,4,6};
    sort(arr, 0, arr.length - 1);
    for (int i : arr) {
        System.out.print(i + " ");
    }
}

private static void sort(int[] arr, int l, int r) {
    int i = l;
    int j = r;
    if (l < r) {
        while (l < r) {
            while (l < r && arr[r] >= arr[l]) {
                r--;
            }
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

            while (l < r && arr[l] <= arr[r]) {
                l++;
            }
            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

        }
        sort(arr, i, l - 1);//递归左边,此时l=5
        sort(arr, l + 1, j);//递归右边,此时l=5
    }
}

 

2.那么c++的代码会是怎么样呢?

#include "pch.h"
#include <iostream>

using namespace std;

void sortQ(int *arr, int l, int r) {
   int i = l;
   int j = r;
   int tmp;
   if (i < j) {
      while (l < r) {
         while (l < r && arr[r] >= arr[l])
         {
            r--;
         }

         tmp = arr[l];
         arr[l] = arr[r];
         arr[r] = tmp;

         while (l < r && arr[r] >= arr[l]) {
            l++;
         }
         tmp = arr[l];
         arr[l] = arr[r];
         arr[r] = tmp;
      }

      sortQ(arr, i, l - 1);//处理左边,此时l=5
      sortQ(arr, l + 1, j);//处理右边,此时l=5
   }

}

int main()
{
    std::cout << "Hello World!\n"; 

   int arr[] = {5,2,1,8,9,3,7,0,4,6};
   int size = sizeof(arr) / sizeof(arr[0]);

   sortQ(arr, 0, size - 1);
   for (int i : arr) {
      cout << i << " ";
   }

}

 

 

 

使用C/C++新建了一个类似于Java的StringBuffer类

使用C/C++新建了一个类似于Java的StringBuffer类,主要实现了常规的几种方法:

1.StringBuffer & append(const char * _c) ;
这个方法是往字符串中插入字符到最后;

2.StringBuffer(const StringBuffer & buf);
在C语言中如果需要使用到a=b这种赋值方法,并且数据成员使用指针形式,那么则需要自定义一个复制函数;

3.char* toString();
返回数据成员中的char数据;

4.int length();
返回字符串的长度;

5.std::string substr(int start = 0,int len = 1);
截取字符串,通常需要借助indexOf的方法来查找字符串的位置;

6.void replaceAll(const char * find, const char * des);
替换字符串中的指定文字;

7.int indexOf(const char * find);
查找指定字符串的位置,如果没有则返回-1;

8.bool operator==(const StringBuffer & buf);
C/C++中特有的方法,如果需要使用运算符:a==b,增需要定义一个自定义的运算符方法,这里只定义了:==。

 

接着就是贴出头文件:StringBuffer.h

#pragma once
#include<iostream>

//exmple:
/*
// StringBuffer sb;
// or like this:
// StringBuffer sb("test");
// sb.append("append.");

// and you can like this:
// sb.append("append 1,").append("append 2,");

// equal:
// sb1==sb?1:0
// if(sb1 == sb){//do something...}

// length:
// sb.length();

// substring:
// sb.substr(int strat,int end);
// sb.substr(0,1);//it will be return "t";

// find:
// sb.indexOf(char * find_char);
// sb.indexOf("st");//it will be return 2;
// sb.indexOf("index");//it will be return -1;

// replaceAll:
// sb.replaceAll(char * find_char,char * des_char);
// like this:
// sb.replaceAll("test","1234");

// toString:
// sb.toString();
*/

#ifndef STRING_BUFFER
#define STRING_BUFFER

class StringBuffer
{
   private:
      char * value;
      char * value1;
      int len;
      int _number;
   public:
      StringBuffer();
      StringBuffer(const char * _c);
      StringBuffer & append(const char * _c) ;
      StringBuffer(const StringBuffer & buf);
      char* toString();
      int length();
      std::string substr(int start = 0,int len = 1);
      void replaceAll(const char * find, const char * des);
      int indexOf(const char * find);
      bool operator==(const StringBuffer & buf);
      ~StringBuffer();
};

#endif // !STRING_BUFFER



然后贴出代码:

#include "pch.h"
#include "StringBuffer.h"
#include<iostream>
#include<string.h>


StringBuffer::StringBuffer()
{
   len = 1;
   _number = 0;
   value = new char[2]{"\0"};
}

StringBuffer::StringBuffer(const char * _c) {
   len = std::strlen(_c) + 1;
   _number = 1;
   value = new char[len];
   strcpy_s(value, len, _c);
}

StringBuffer::StringBuffer(const StringBuffer & buf) {
   len = buf.len;
   _number = buf._number;
   value = new char[len];
   strcpy_s(value, len, buf.value);
}

StringBuffer::~StringBuffer()
{
   delete[] value;
   std::cout << "StringBuffer out." << std::endl;
}

StringBuffer & StringBuffer::append(const char * _c) {
   int _l = std::strlen(_c)+1;
   value1 = new char[len+_l];
   strcpy_s(value1, len, value);
   strcat_s(value1, len + _l, _c);

   value = value1;
   
   len += _l;
   _number++;
   return *this;
}

char* StringBuffer::toString() {
   return this->value;
}

int StringBuffer::length() {
   return strlen(value);
}

std::string StringBuffer::substr(int start, int len) {
   std::string s = value;
   return s.substr(start, len);
}

int StringBuffer::indexOf(const char * find) {
   std::string s = value;
   return s.find(find);
}

void StringBuffer::replaceAll(const char * find, const char * des) {
   int idx = 0;
   int _len = std::strlen(find);
   bool has = false;
   std::string s = value;
   while (idx > -1)
   {
      idx = s.find(find);
      if (idx > -1) {
         s = s.replace(idx, _len, des);
         has = true;
      }
   }

   if (has) {
      strcpy_s(value, strlen(s.data()) + 1, s.data());
      len = strlen(s.data()) + 1;
      value1 = value;
   }
   
}

bool StringBuffer::operator==(const StringBuffer & buf) {
   if (this == &buf) {
      return true;
   }
   return strcmp(this->value, buf.value) == 0;
}

来一张效果图呗:

QQ截图20181118163945

C/C++关键字typedef使用指南

搞懂了c++创始人写的中的下面这个例子, 有助于你理解typdef:

typedef int P();
typedef int Q();
class X {
static P(Q); // 等价于`static int Q()`, Q在此作用域中不再是一个类型
static Q(P); // 等价于`static int Q(int ())`, 定义了一个名为Q的function
};

这是一个极好的例子, 先问一下 typedef int P()到底做了什么 ? 其实是 :

declares a function type P as returning an int and taking no arguments.

1. 官方定义

初次接触此类typedef用法的程序员直观上理解这个例子比较困难, 我们来看一下typedef的官方定义 :

Typedef does not work like typedef [type] [new name].The[new name] part does not always come at the end.

You should look at it this way : if[some declaration] declares a variable, typedef [same declaration] would define a type.

总结一下就是 : 任何声明变量的语句前面加上typedef之后,原来是变量的都变成一种类型。不管这个声明中的标识符号出现在中间还是最后。

2. 隐藏技能
typedef 定义的新类型, 使用时可以省略括号。什么意思 ?

typedef int NUM;
NUM a = 10; // 也可写成`NUM(a) = 10;
NUM(b) = 12; // 也可写成`NUM b = 12;

3. 例子(先从初级的开始 :)

int整型

typedef int x; // 定义了一个名为x的int类型

自定义结构体

typedef struct { char c; } s; // 定义名为s的struct类型

指针

typedef int *p; //定义了一个名为p的指针类型, 它指向int

高级的(注意标识符不一定在最后) :

数组

typedef int A[]; // 定义一个名为A的int数组的类型

函数

typedef int f(); // 定义一个名为f, 参数为空, 返回值为int的函数类型

typedef int g(int); // 定义一个名为g, 含一个int参数, 返回值为int行的函数类型

现在回过头看:

typedef int P();
static P(Q);

应该就比较好理解了, P是一个新定义的function类型, 它返回值为int, 无参数
根据我的第2点说明, P(Q); 实际上等价于P Q, 声明Q是一个返回值为int, 无参数的函数.

这玩意有什么用呢 ?
我们都知道C++语言里, 函数都是先声明后使用的(除非在使用之前定义), 看以下例子 :

#include <iostream>
#include <stdio.h>
#include <string>

typedef int P(); // 简单的
typedef void Q(int *p, const std::string& s1, const std::string& s2, size_t size, bool is_true); // 复杂的
class X {
public:
P(eat_shit); // 等价于声明`int eat_shit();`
Q(bullshit); // 等价于声明`void bullshit(int *p, const string& s1, const string& s2, size_t size, bool is_true);`
};

int main() {
X *xx;
printf(“shit ret: %d\n”, xx->eat_shit());
int a[] = { 1, 3, 4, 5, 7 };
xx->bullshit(a, “foo”, “bar”, sizeof(a) / sizeof(int), true);
}

int X::eat_shit() {
return 888;
}

void X::bullshit(int *p, const std::string& s1, const std::string& s2, size_t size, bool is_true) {
std::cout << “s1: ” << s1 << “, s2: ” << s2 << “, size: ” << size << std::endl;
printf(“elems:\n”);
for (int i = 0; i < size; i++) {
printf(“%d %s”, *p++, (i == size – 1) ? “” : “,”);
}
printf(“\n”);
}

理解了上面的再看下面这段,理解复杂的定义和声明:

在阅读Linux的内核代码是经常会遇到一些复杂的声明和定义,例如:

  1.  void * (*(*fp1) (int))[10];
  2. float(*(*fp2) (int, int, float)) (int);
  3. typedef double(*(*(*fp3) ())[10]) ();
    1. fp3 a;
  4. int(*(*fp4())[10]) ();

 

刚看到这些声明或者定义时,初学者可能头皮发毛,基于大惑不解。如果缺乏经验和方法来对这些内容进行理解,势必会让我们浪费大量的时间。

我尝试对这些内容进行疏理和总结,为自己和有同样困惑的同学答疑解惑。要理解这些复杂的声明和定义,我觉得首先不能着急,应该由浅而深,逐步突破。下面先看一些简单的定义:

1. 定义一个整型数

int a;

2. 定义一个指向整型数的指针

int *p;

3. 定义一个指向指针的指针,它指向的指针指向一个整型数

int **pp;

我们可以用一些简单的代码把这三条给串起来:

int a;
int *p;
int **pp;

p = &a; // p指向整数a所在的地址
pp = &p; // pp指向指针p

 

4. 定义一个包含10个整型数的数组

int arr[10];

5. 定义一个指向包含10个整型数数组的指针

int(*pArr)[10];

用几行代码将4、5两个定义串起来:

int arr[10];
int(*pArr)[10];

pArr = &arr;

6. 定义一个指向函数的指针,被指向的函数有一个整型参数并返回整型值

int(*pfunc) (int);

7. 定义一个包含10个指针的数组,其中包含的指针指向函数,这些函数有一个整型参数并返回整型值

int(*arr[10]) (int);

用几行代码将6、7两个定义串起来:

int(*pfunc) (int);
int(*arr[10]) (int);

arr[0] = pfunc;

到这一步,似乎就不是那么好理解了。现在需要请出用于理解复杂定义的“右左法则”:

从变量名看起,先往右,再往左,碰到圆括号就调转阅读的方向;括号内分析完就跳出括号,还是先右后左的顺序。如此循环,直到分析完整个定义。

让我们用这个方法来分析上面的第6条定义:int(*pfunc) (int);

  • 找到变量名pfunc,先往右是圆括号,调转方向,左边是一个*号,这说明pfunc是一个指针;
  • 然后跳出这个圆括号,先看右边,又遇到圆括号,这说明(*pfunc)是一个函数,所以pfunc是一个指向这类函数的指针,即函数指针,这类函数具有一个int类型的参数,返回值类型是int。

接着分析第7条定义:int(*arr[10]) (int);

  • 找到变量名arr,先往右是[]运算符,说明arr是一个数组;
  • 再往左是一个*号,说明arr数组的元素是指针(注意:这里的*修饰的不是arr,而是arr[10]。原因是[]运算符的优先级比*要高,arr先与[]结合。);
  • 跳出圆括号,先往右又遇到圆括号,说明arr数组的元素是指向函数的指针,它指向的函数有一个int类型的参数,返回值类型是int。

分析完这两个定义,相信多数人心里面应该有点谱了。

可应该还有人会问:怎么判断定义的是函数指针(定义6),还是数组指针(定义5),或是数组(定义7)?可以抽象出几个模式:

  • type(*var)(…); // 变量名var与*结合,被圆括号括起来,右边是参数列表。表明这是函数指针
  • type(*var)[]; //变量名var与*结合,被圆括号括起来,右边是[]运算符。表示这是数组指针
  • type(*var[])…; // 变量名var先与[]结合,说明这是一个数组(至于数组包含的是什么,由旁边的修饰决定)

至此,我们应该有能力分析文章开始列出来了几条声明和定义:

(1) void * (*(*fp1) (int))[10];

  • 找到变量名fp1,往右看是圆括号,调转方向往左看到*号,说明fp1是一个指针;
  • 跳出内层圆括号,往右看是参数列表,说明fp1是一个函数指针,接着往左看是*号,说明指向的函数返回值是指针;
  • 再跳出外层圆括号,往右看是[]运算符,说明函数返回的是一个数组指针,往左看是void *,说明数组包含的类型是void *。

简言之,fp1是一个指向函数的指针,该函数接受一个整型参数并返回一个指向含有10个void指针数组的指针。

(2) float(*(*fp2) (int, int, float)) (int);

  • 找到变量名fp2,往右看是圆括号,调转方向往左看到*号,说明fp2是一个指针;
  • 跳出内层圆括号,往右看是参数列表,说明fp2是一个函数指针,接着往左看是*号,说明指向的函数返回值是指针;
  • 再跳出外层圆括号,往右看还是参数列表,说明返回的指针是一个函数指针,该函数有一个int类型的参数,返回值类型是float。

简言之,fp2是一个指向函数的指针,该函数接受三个参数(int, int和float),且返回一个指向函数的指针,该函数接受一个整型参数并返回一个float。

(3) typedef double(*(*(*fp3) ())[10]) ();

fp3 a;

  • 如果创建许多复杂的定义,可以使用typedef。这一条显示typedef是如何缩短复杂的定义的。
  • 跟前面一样,先找到变量名fp3(这里fp3其实是新类型名),往右看是圆括号,调转方向往左是*,说明fp3是一个指针;
  • 跳出圆括号,往右看是空参数列表,说明fp3是一个函数指针,接着往左是*号,说明该函数的返回值是一个指针;
  • 跳出第二层圆括号,往右是[]运算符,说明函数的返回值是一个数组指针,接着往左是*号,说明数组中包含的是指针;
  • 跳出第三层圆括号,往右是参数列表,说明数组中包含的是函数指针,这些函数没有参数,返回值类型是double。

简言之,fp3是一个指向函数的指针,该函数无参数,且返回一个含有10个指向函数指针的数组的指针,这些函数不接受参数且返回double值。

这二行接着说明:a是fp3类型中的一个。

(4) int(*(*fp4())[10]) ();

这里fp4不是变量定义,而是一个函数声明。

  • 找到变量名fp4,往右是一个无参参数列表,说明fp4是一个函数,接着往左是*号,说明函数返回值是一个指针;
  • 跳出里层圆括号,往右是[]运算符,说明fp4的函数返回值是一个指向数组的指针,往左是*号,说明数组中包含的元素是指针;
  • 跳出外层圆括号,往右是一个无参参数列表,说明数组中包含的元素是函数指针,这些函数没有参数,返回值的类型是int。

简言之,fp4是一个返回指针的函数,该指针指向含有10个函数指针的数组,这些函数不接受参数且返回整型值。

用typedef简化复杂的声明和定义,以上我们已经看到了不少复杂的声明和定义,这里再举一个例子:

int *(*a[10]) (int, char*);

  • 用前面的“右左法则”,我们可以很快弄清楚:
  • a是一个包含10个函数指针的数组,这些函数的参数列表是(int, char*),返回值类型是int*。
  • 理解已经不成问题,这里的关键是如果要定义相同类型的变量b,都得重复书写:

int *(*b[10]) (int, char*);

这里有没有方便的办法避免这样没有价值的重复?答案就是用typedef来简化复杂的声明和定义。

typedef可以给现有的类型起个别名。这里用typedef给以上a、b的类型起个别名:

typedef int *(*A[10]) (int, char*); // 在之前定义的前面加入typedef,然后将变量名a替换成类型名A

现在要再定义相同类型的变量c,只需要:
A c;

再看一例:

void(*b[10]) (void(*)());

先替换右边括号里面的参数,将void(*)()的类型起个别名pParam: