总述

它能把图像上的颜色一一列举出来。这个过程其实被称为图像的颜色提取，中位切分法就是针对该过程的算法之一。这个过程更专业一点的称谓应该是颜色的量化过程，量化一词不仅仅限于颜色，它适用于一切连续的量，而量化其实就是把连续的量转换成离散的量的过程。于是准确概括就是，中位切分法是一种针对图像的颜色量化算法。

演示.gif

图像是什么？

图像，就是照片嘛。你能通过它的内容接收到一些信息，有用的，没用的，好的，还是坏的，看你自己。但是，如果你从颜色的角度看，图像其实是各种颜色容器，你之所以能看到各种各样的图像，只不过是因为这些颜色的种类不同，数量不同，以及排列组合的形式不同而已。

什么是真彩色？

其实很简单，真彩色是用4个颜色的分量来表示的，分别是R(Red:红)、G(Green:绿)、B(Blue:蓝)、A(Alpha:透明度)，每个分量占用了1个字节，所以真彩色中每个颜色要用4字节表示，于是有2³²种颜色。
然而，人眼并不需要如此多的颜色种类，256种足够了。
很显然2⁸=256于是表示某种颜色只需要1byte，但是这其实只不过是个标识，这个标识应该指向一个具体的颜色的列表。
也就是说，这个列表里面的颜色都已经是确定了啦，就是256种不同的颜色。每次要取一种颜色只需要根据这个标识到列表中去取出来就可以了。

什么是颜色空间？

空间一般指三维空间，就是立体几何那个玩意，空间坐标系，就XYZ那玩意。现在假设不考虑透明度，只考虑RGB分量，那么每个分量就自成一条坐标轴了，于是RGB坐标轴就形成了一个立体的坐标系，这个坐标系就是所谓的颜色空间。大家都知道XYZ坐标体系中的点都可以三维坐标来表示——(x,y,z)，同理，颜色空间中的颜色都能用颜色坐标来表示，即(r,g,b)。

图像的映射

正如上面所说，图像是各种颜色的容器，而颜色又可以被映射到颜色空间。于是，图像中，从r分量的角度来看，在各种颜色组成的集合中，必有最大的r分量值和最小的r分量值，于是从最大的r值到最小的r值形成了一条边。同理，最大的g值到最小的g值又形成了一条边，最大的b值到最小的b值还是形成了一条边，于是3条边就形成了1个立方体。图像中所有的颜色都处于这个立方体中。

立方体的分裂

现在说的立方体并不仅限于第一个立方体，而是任何一个立方体。立方体嘛，肯定有个最长边，或者最长边不止一个，反正就是找到最长的边就是了。不过这样说有点抽象，说得直接一点就是找到RGB分量中最大值最小值相差最大的那个分量。
这个分量一旦知道了，你就可以把当前立方体中的颜色值按照该分量进行排序了。因为获取某分量最大值和最小值只需要比较而已，但是该分量对应的颜色值还是无序的，你应该排序。

为什么要排序呢？

因为一排序，该分量就成了有序了，而有序就形成了该分量的梯度变化，而梯度变化的极限就是渐变。3个分量都是梯度变化以后，那么各个颜色值也就成了逐渐的变化的形式了。

该怎么分裂？

你知道每种颜色都对应至少1个像素，你需要把这些数量的像素一分为二。按照某个分量排好序以后，你需要把当前立方体中该分量较高的和较低的像素分开，并且这两部分的像素数量尽量相等，没错这就是分裂所要达到的目的。

这个分裂有啥用？

这样做你可以把像素均匀地分布到各个颜色立方体中，分裂到最后的立方体可以得到该立方体的代表色，也就是说该立方体中所有的像素点都是这样个颜色了，即，颜色接近的像素点被集中到了一起。仔细想一下你会发现这样做并不会让图像所表达的内容变化太大，不会变化太大就是说你现在所分裂出来的所有的小立方体所代表的颜色已经足够接近图像上面的各个颜色了，当然，分裂出来的小立方体越多就越接近原图像中的各个颜色。
如此一来用中位切分法获取图像各个颜色的原理解释完毕。

适用于部分数组排序的堆排序

这是个工具，不仅仅能排序整个数组，还能排序部分数组，很方便实用，需要的尽管拿去。

+ (void)heapSort:(NSMutableArray *)sourceArray
      startIndex:(NSInteger)startIndex
  subarrayLength:(NSInteger)length {
    for (NSInteger counter = length / 2 - 1 + startIndex; counter > startIndex - 1; counter--) {
        [HeapSort adjust:sourceArray
              startIndex:startIndex
               rootIndex:counter
            adjustLength:length];
    }
    for (NSInteger counter = startIndex + length - 1; counter > startIndex; counter--) {
        [sourceArray exchangeObjectAtIndex:startIndex
                         withObjectAtIndex:counter];
        [HeapSort adjust:sourceArray
              startIndex:startIndex
               rootIndex:startIndex
            adjustLength:counter - startIndex];
    }
}

+ (void)adjust:(NSMutableArray *)souceArray
    startIndex:(NSInteger)startIndex
     rootIndex:(NSInteger)rootIndex
  adjustLength:(NSInteger)adjustLength {
    for (NSInteger count = rootIndex; count < adjustLength / 2 + startIndex;) {
        NSInteger leftChildIndex = 2 * (count - startIndex) + 1 + startIndex;
        NSInteger rightChildIndex = leftChildIndex + 1;
        NSInteger smallerPointer = leftChildIndex;
        if (rightChildIndex < adjustLength + startIndex) {
            NSComparisonResult compareResult = [souceArray[leftChildIndex] compare:souceArray[rightChildIndex]];
            if (compareResult == NSOrderedDescending) {
                smallerPointer = rightChildIndex;
            }
        }
        NSComparisonResult compareResult = [souceArray[count] compare:souceArray[smallerPointer]];
        if (compareResult == NSOrderedDescending) {
            [souceArray exchangeObjectAtIndex:count withObjectAtIndex:smallerPointer];
            count = smallerPointer;
        } else break;
    }
}

源代码

这是基于iOS平台，用Objective-C编的，需要用XCode运行的工程，别搞错了。
点此下载