快速排序的python、java、javascript实现

末蓝、 2023-01-15 03:58 113阅读 0赞

## 概述 ##

快速排序与冒泡排序的相似处是都采取了临近比较、交换两值的方式，快速排序的特点在于运用了`分治法`，每次都将数组分成两个部分，与一个`基准元素`进行比较，比标志位大的放在标志位的右边，比标志位小的放在标志位的左边。`基准元素`的选择可以是简单的使用列表的第一个元素，也可以任意进行选择。

## 快速排序的python实现 ##

def quickFixedFinal(startIndex, endIndex, arr=[]):
        if startIndex >= endIndex:
            return
        base = findBase(startIndex, endIndex, arr)
        # 递归分治
        quickFixedFinal(startIndex, base-1, arr)
        quickFixedFinal(base+1, endIndex, arr)
    
    def findBase(startIndex, endIndex, arr=[]):
    	# 取列表的第一个元素作为基准元素
        startIndexCopy = startIndex
        while startIndex != endIndex:
        	# 右指针移动
            while startIndex < endIndex and arr[endIndex] > arr[startIndexCopy]:
                endIndex -= 1
            # 左指针移动
            while startIndex < endIndex and arr[startIndex] <= arr[startIndexCopy]:
                startIndex += 1
            if startIndex < endIndex:
                arr[startIndex], arr[endIndex] = arr[endIndex], arr[startIndex]
    	
    	# 交换指针重合点和基准元素
        arr[startIndexCopy], arr[startIndex] = arr[startIndex], arr[startIndexCopy]
    
        return startIndex
    
    
    arr = [3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11]
    
    quickFixedFinal(0, len(arr)-1, arr)
    print(arr)

## 快速排序的java实现 ##

import java.util.Arrays;
    
    public class Quick { 
        public static void quick(int startIndex,int endIndex,int[] arr ){ 
            if(startIndex >= endIndex){ 
                return;
            }
            int base = getBase(startIndex,endIndex,arr);
            quick(startIndex,base-1,arr);
            quick(base+1,endIndex,arr);
        }
        public static int getBase(int startIndex,int endIndex,int[] arr){ 
            int startIndexCopy = startIndex;
            while (startIndex != endIndex){ 
                while (startIndex < endIndex && arr[endIndex] > arr[startIndexCopy]){ 
                    endIndex--;
                }
                while (startIndex < endIndex && arr[startIndex] <= arr[startIndexCopy]){ 
                    startIndex++;
                }
                if(startIndex < endIndex){ 
                    int tmp = arr[startIndex];
                    arr[startIndex] = arr[endIndex];
                    arr[endIndex] = tmp;
                }
            }
            int tmp = arr[startIndexCopy];
            arr[startIndexCopy] = arr[startIndex];
            arr[startIndex] = tmp;
    
            return startIndex;
        }
        public static void main(String[] args){ 
            int[] arr = new int[]{ 3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11};
            quick(0,arr.length-1,arr);
            System.out.println(Arrays.toString(arr));
        }
    }

## 快速排序的javascript实现 ##

## 爬坑纪 ##

def quick(startIndex,endIndex,arr=[]):
    
        if(startIndex >= endIndex):
            return
    
        base = findBase(startIndex,endIndex,arr)
        quick(startIndex,base-1,arr)
        quick(base+1,endIndex,arr)
    
    
    def findBase(startIndex,endIndex,arr=[]):
        initBase = arr[startIndex]
        while(startIndex != endIndex):
            while(startIndex < endIndex and arr[startIndex] < initBase):
                startIndex+=1
            while(startIndex < endIndex and arr[endIndex] > initBase):
                endIndex-=1
            if(startIndex < endIndex):
                arr[startIndex],arr[endIndex] = arr[endIndex],arr[startIndex]
        arr[startIndex],initBase = initBase,arr[startIndex]
        return startIndex
    
    
    list = [3,4,14,1,5,6,7,8,-1,0,9,11]
    
    quick(0,len(list)-1,list)
    print(list)

这段代码初看没有什么问题，但是忽略了重复元素。如果列表中存在重复元素，则在函数`findBase`中`while`将会是死循环，尝试修复这个问题，像下面这样：

while(startIndex != endIndex):
        while(startIndex < endIndex and arr[startIndex] <= initBase):
            startIndex+=1
    	...

得到的结果却非常奇怪：\[3, 3, 3, 3, 3, 6, 6, 6, 14, 14, 14, 14\]

再仔细看，发现

def findBase(startIndex,endIndex,arr=[]):
    	initBase = arr[startIndex]
    	...
    	arr[startIndex],initBase = initBase,arr[startIndex]

`findBase`再将指针重合点和列表基准元素进行交换的时候是有问题的，将`arr[startIndex]`赋值给`initBase`，后面进行赋值时候，指针重合点`arr[startIndex]`赋值给的变量`initBase`，而不是列表基准元素。

再次进行修改：

def findBase(startIndex, endIndex, arr=[]):
        startIndexCopy = startIndex
        while startIndex != endIndex:
            while startIndex < endIndex and arr[endIndex] > arr[startIndexCopy]:
                endIndex -= 1
            while startIndex < endIndex and arr[startIndex] <= arr[startIndexCopy]:
                startIndex += 1
            if startIndex < endIndex:
                arr[startIndex], arr[endIndex] = arr[endIndex], arr[startIndex]
    
        arr[startIndexCopy], arr[startIndex] = arr[startIndex], arr[startIndexCopy]
    
        return startIndex

此时结果为：\[-1, 0, 1, 1, 3, 4, 5, 6, 7, 8, 9, 11, 14\]，无误。