正负数排序

蔚落 2022-08-08 12:44 15阅读 0赞

#!/usr/bin/python
    #coding=utf8
    '''
    time 2015.05.16
    refer http://blog.csdn.net/bestwolf1983/article/details/9157621
    '''
    
    def sort_positive_negative(data_list):
    '''
    @brief:将数组里的负数排在数组的前面，正数排在数组的后面，但不改变原先负数和正数的排列顺序；时间复杂度为o(n^2),空间复杂度为o(1)
    @param data_list:待排序的数组
    @return:None
    '''
    	print(data_list)
    	length = len(data_list)
    	head = 0 #自然数开始的下标
    	while data_list[head] <= 0: #找到第一个自然数
    		head += 1
    	tail = head + 1 #已经有序的自然数后面的负数的下标
    	while head < length:
    		while data_list[tail] >= 0: #找到有序自然数后面的第一个负数
    			if tail == length - 1:
    				break
    			tail += 1
    		if data_list[tail] >= 0: #如果找不到负数，那么数组已经有序
    			break
    		temp = data_list[tail] #保存负数
    		for i in xrange(tail, head, -1): #循环后移已有序的自然数，为负数腾出空间
    			data_list[i] = data_list[i-1]
    		data_list[head] = temp #将负数填充到最终的位置,一次循环会确定一个负数的最终位置
    		head += 1
    		print(data_list)
    
    '''
    @brief:将数组里的负数排在数组的前面，正数排在数组的后面，但不改变原先负数和正数的排列顺序；时间复杂度为o(n),空间复杂度为o(1)
    @param data_list:待排序的数组
    @return:None
    '''
    def sort_positive_negative1(data_list):
            i = 0
            j = len(data_list)-1
            while(i < j):
                while i < j:
                    if data_list[i] >= 0:
                        break
                    else:
                        i = i + 1
                while i < j:
                    if data_list[j] <= 0:
                        break
                    else:
                        j = j -1
                r = data_list[i]
                data_list[i] = data[j]
                data_list[j] = r
            print data_list
    
    if __name__ == "__main__":
    	data_list = [-5, 2, -3, 4, -8, 0, -9, 1, 3, -10, 22, 33, 44, 55, -10]
    	sort_positive_negative(data_list)